|
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.
|