Morris, Walter D.
Rights / licenseIn Copyright - Non-Commercial Use Permitted
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 nding 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 rst expected linear-time algorithms for solving PGLCP with a xed number of blocks Show more
External linksSearch via SFX
Journal / seriesTechnical report
PublisherETH, Department of Computer Science
SubjectANORDNUNGEN GEOMETRISCHER GEBILDE (GEOMETRIE); PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; ARRANGEMENTS OF GEOMETRIC FIGURES (GEOMETRY); PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME
Organisational unit02150 - Departement Informatik / Department of Computer Science
NotesTechnical Reports D-INFK.
MoreShow all metadata