Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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

K-Matrix Linear Complementarity Problems and Unique Sink Orientations

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login