Linear programming and unique sink orientations

DOI10.1145/1109557.1109639zbMath1192.90121OpenAlexW4235083118MaRDI QIDQ3581590

Ingo Schurr, Bernd Gärtner

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109639

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations ⋮ Directed random walks on polytopes with few facets ⋮ Unique end of potential line ⋮ Realizability makes a difference: a complexity gap for sink-finding in USOs ⋮ Counting unique-sink orientations ⋮ Random sampling with removal ⋮ Unique sink orientations of grids ⋮ Enumeration of PLCP-orientations of the 4-cube ⋮ Violator spaces: Structure and algorithms ⋮ An exponential lower bound for Cunningham's rule ⋮ Unnamed Item ⋮ Unique End of Potential Line