Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 30, 2009, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Bernd Gärtner
The linear complementarity problem (LCP) is the following: given a square matrix M and a vector q, find nonnegative vectors w and z such that w - Mz = q and w^T z = 0. The question whether such w and z exist is NP-complete in general. If M is a P-matrix (all principal minors are positive), there are unique solution vectors w and z, but the computational complexity of finding them is unknown.
On a combinatorial level, the P-matrix LCP can be studied using the concept of unique sink orientations of cubes (USO). Recent research has focused on the translation of algebraic properties of the matrix M into combinatorial properties of the underlying USO. We will report on one result along these lines. If M is a K-matrix (a P-matrix such that all off-diagonal entries are nonpositive), the underlying USO contains short directed paths only. This generalizes (and at the same time combinatorially explains) the known result that K-matrix LCPs are polynomial-time solvable.
Joint work with Jan Foniok, Komei Fukuda and Hans-Jakob Lüthi.
Automatic MiSe System Software Version 1.4803M | admin login