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 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. For a full paper see [1].