Unique Sink Orientations of Grids

We introduce unique sink orientations of grids as digraph models for many well-studied problems, including linear programming over products of simplices, generalized linear complementarity problems over P-matrices (PGLCP), and simple stochastic games. 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 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. The first and the third author acknowledge support from the Swiss Science Foundation (SNF), Project No. 200021-100316/1. Part of this research was done at the 2004 Barbados Undercurrent Workshop Polyhedra, Convex Geometry, and Optimization at Bellairs Research Institute, McGill University.