# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__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

## 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: 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