Tutte seminar - Naonori Kakimura

Friday, March 7, 2008 3:30 pm - 4:30 pm EST (GMT -05:00)

Sign-Solvability of Linear Programming and Linear Complementarity Problems

Speaker: Naonori Kakimura
Affiliation: University of Tokyo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

This talk presents an attempt to connect qualitative matrix theory with linear programming and linear complementarity problems.
A linear program max{cx | Ax=b, x>=0} is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. Checking the sign-solvability of a given linear program turns out to be co-NP-complete. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c. Similarly, we introduce sign-solvability for linear complementarity problems (LCPs). We show that a totally sign-nonsingular matrix characterizes a sign-solvable LCP whose coefficient matrix is nonzero diagonal. This characterization leads to an efficient algorithm to obtain the sign pattern of a solution for these LCPs.

The first part of this talk is a joint work with Satoru Iwata.

References:

S. Iwata and N. Kakimura: Solving Linear Programs from Sign Patterns, Mathematical Programming, to appear.

N. Kakimura: Sign-Solvable Linear Complementarity Problems, Lecture Notes in Computer Science, Springer-Verlag 4513, pp.397--409, 2007.