| Autor: |
Jünger, Michael, Kaibel, Volker, Gärtner, Bernd, Morris, Walter D., Rüst, Leo |
| Zdroj: |
Integer Programming & Combinatorial Optimization; 2005, p210-224, 15p |
| Abstrakt: |
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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
