Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

We introduce unique sink orientations of grids as digraph models for many well-studied problems, including linear programming over products of simplices and generalized linear complementarity problems over $\P$-matrices (\PGLCP). We investigate the combinatorial structure of such orientations and develop randomized algorithms for finding the sink. We show that the orientations arising from \PGLCP\ satisfy the combinatorial \emph{Holt-Klee} condition known to hold for polytope digraphs, and we give the first expected linear-time algorithms for solving \PGLCP\ with a fixed number of blocks.