Please email any errors or updates to our website support/editor.

PDF files require Adobe Acrobat Reader.

Friday, March 7, 2008 — 3:30 PM to 4:30 PM EST

Speaker: | Naonori Kakimura |
---|---|

Affiliation: | University of Tokyo |

Room: | Mathematics & Computer Building (MC) 5158 |

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.

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.

Location

MC - Mathematics & Computer Building

5158

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

Please email any errors or updates to our website support/editor.

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1