Some \(0/1\) polytopes need exponential size extended formulations
type: Item
instance of: scholarly article
title: Some \(0/1\) polytopes need exponential size extended formulations
zbMATH Open document ID: 1282.90245
author: Thomas Rothvoß
published in: Mathematical Programming. Series A. Series B
publication date: 2014-02-03T00:00:00Z
full work available at URL: https://arxiv.org/abs/1105.0036
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6254059
MaRDI profile type: Publication
OpenAlex ID: W2159584454
arXiv ID: 1105.0036
cites work: Computational Complexity
cites work: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
cites work: Disjunctive programming: Properties of the convex hull of feasible points
cites work: On cuts and matchings in planar graphs
cites work: Approximate formulations for 0-1 knapsack sets
cites work: Extended formulations in combinatorial optimization
cites work: Q4432947
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Linear vs. semidefinite extended formulations
cites work: Extended formulations for polygons
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: An application of simultaneous diophantine approximation in combinatorial optimization
cites work: Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
cites work: Smallest compact formulation for the permutahedron
cites work: Q3050157
cites work: Symmetry Matters for the Sizes of Extended Formulations
cites work: Using separation algorithms to generate mixed integer model reformulations
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: On the Complexity of Nonnegative Matrix Factorization
cites work: Expressing combinatorial optimization problems by linear programs
cites work: Q4518979
DOI: 10.1007/S10107-012-0574-3
description: scientific article