Generating all vertices of a polyhedron is hard
From MaRDI portal
Publication:5901119
DOI10.1145/1109557.1109640zbMath1192.52022OpenAlexW1538859003MaRDI QIDQ5901119
Endre Boros, Vladimir A. Gurvich, Khaled M. Elbassioni, Konrad Borys, Leonid G. Khachiyan
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.1109640
Computational aspects related to convexity (52B55) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A note on systems with max-min and max-product constraints ⋮ Exploiting the polyhedral geometry of stochastic linear bilevel programming ⋮ Parallelization of nullspace algorithm for the computation of metabolic pathways ⋮ A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ On enumerating minimal dicuts and strongly connected subgraphs ⋮ A problem in enumerating extreme points, and an efficient algorithm for one class of polytopes