×

zbMATH — the first resource for mathematics

Linear vs. semidefinite extended formulations, exponential separation and strong lower bounds. (English) Zbl 1286.90125
Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 95-106 (2012).

MSC:
90C27 Combinatorial optimization
90C05 Linear programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI