Linear programming and unique sink orientations

DOI10.1145/1109557.1109639MaRDI QIDQ3581590zbMATH OpenOpenAlexFDO

Authors Ingo Schurr, B. 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)

Cited in

(17)

• Realizability makes a difference: a complexity gap for sink-finding in USOs
• On flipping edge sets in unique sink orientations
• The complexity of all-switches strategy improvement
• Counting unique-sink orientations
• Realizability in Matoušek unique sink orientations: characterization and complexity gap
• Violator spaces: Structure and algorithms
• Enumeration of PLCP-orientations of the 4-cube
• Unique End of Potential Line
• Unique end of potential line
• Unique sink orientations of grids
• Random sampling with removal
• A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
• Two choices are enough for P-LCPs, USOs, and colorful tangents
• An unconditional lower bound for the active-set method on the hypercube
• Directed random walks on polytopes with few facets
• A unified worst case for classical simplex and policy iteration pivot rules
• An exponential lower bound for Cunningham's rule

This page was built for publication: Linear programming and unique sink orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581590)