## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, July 02, 2009, 12:15 pm

Duration: This information is not available in the database

Location: CAB G51

Speaker: Lorenz Klaus

## On the Number of Unique-Sink Orientations Arising from Pivoting in Linear Complementarity

For the P-matrix linear complementarity problem (P-LCP) neither hardness results nor polynomial-time algorithms are known. We focus on simple principal pivoting algorithms, identified by a pivot rule, as solving methods. The combinatorial unique-sink orientation (USO) abstraction is employed for the study of their behavior. By determining bounds on the number of USOs arising from P-LCPs (P-USOs) we estimate the chances whether a polynomial-time pivot rule for the P-LCP is likely to exist. The number of P-USOs in dimension $n$ turns out to be at most $2^{O(n^{3})}$, and for a lower bound, an explicit construction scheme gives $2^{\Omega(n^{2})}$ LP-realizable USOs. We conclude that the P-USOs contain a lot of combinatorial structure which is unknown so far, because every previously studied combinatorially defined class of USOs is much larger. The goal of future research is to extract this structure in order to prove polynomial runtime of an existing pivot rule or to devise superior rules.

Information for students and suggested topics for student talks