Exponential lower bounds for polytopes in combinatorial optimization
type: Item
instance of: scholarly article
zbMATH Open document ID: 1333.90107
DOI: 10.1145/2716307
author: Samuel Fiorini
author: Sebastian Pokutta
author: Hans Raj Tiwary
author: Serge Massar
author: Ronald de Wolf
published in: Journal of the ACM
publication date: 2016-03-24T00:00:00Z
full work available at URL: https://arxiv.org/abs/1111.0837
full work available at URL: https://ir.cwi.nl/pub/25730
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 68Q12
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6560185
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: communication complexity
zbMATH Keywords: linear programming
zbMATH Keywords: quantum communication complexity
zbMATH Keywords: semidefinite programming
MaRDI profile type: Publication
OpenAlex ID: W1755753347
arXiv ID: 1111.0837
cites work: Lower Bounds for Local Search by Quantum Arguments
cites work: Lattice problems in NP ∩ coNP
cites work: On the extension complexity of combinatorial polytopes
cites work: Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
cites work: A lift-and-project cutting plane algorithm for mixed 0-1 programs
cites work: Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
cites work: Approximation Limits of Linear Programs (Beyond Hierarchies)
cites work: Average case polyhedral complexity of the maximum stable set problem
cites work: Information-theoretic approximations of the nonnegative rank
cites work: Common information and unique disjointness
cites work: An information complexity approach to extended formulations
cites work: On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity
cites work: Q3002766
cites work: Approximate Constraint Satisfaction Requires Large LP Relaxations
cites work: Integrality gaps for Sherali-Adams relaxations
cites work: Extended formulations in combinatorial optimization
cites work: The cut polytope and the Boolean quadric polytope
cites work: Geometry of cuts and metrics
cites work: Extended formulations, nonnegative factorizations, and randomized communication protocols
cites work: Q2934582
cites work: Combinatorial bounds on nonnegative rank and extended formulations
cites work: Generalized probabilistic theories and conic extensions of polytopes
cites work: Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
cites work: Optimal Sherali-Adams Gaps from Pairwise Independence
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Theta Bodies for Polynomial Ideals
cites work: Lifts of Convex Sets and Cone Factorizations
cites work: A counterexample to the Alon-Saks-Seymour conjecture and related problems
cites work: Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
cites work: Symmetry Matters for the Sizes of Extended Formulations
cites work: A short proof that the extension complexity of the correlation polytope grows exponentially
cites work: A new polynomial-time algorithm for linear programming
cites work: Exponential lower bound for 2-query locally decodable codes via a quantum argument
cites work: Q3050157
cites work: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
cites work: Communication Complexity
cites work: The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
cites work: On the complexity of communication complexity
cites work: Lower Bounds on the Size of Semidefinite Programming Relaxations
cites work: On the Shannon capacity of a graph
cites work: Q4407449
cites work: Communication complexity and combinatorial lattice theory
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Quantum Computer Science
cites work: Q2706552
cites work: A note on the extension complexity of the knapsack polytope
cites work: On the distributional complexity of disjointness
cites work: The Matching Polytope has Exponential Extension Complexity
cites work: Q3549626
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Q3392273
cites work: Reformulation and Decomposition of Integer Programs

Exponential lower bounds for polytopes in combinatorial optimization (cites work)
cites work: Quantum communication and complexity.

Exponential lower bounds for polytopes in combinatorial optimization (cites work)
cites work: Nondeterministic Quantum Query and Communication Complexities

Exponential lower bounds for polytopes in combinatorial optimization (cites work)
cites work: Expressing combinatorial optimization problems by linear programs

Exponential lower bounds for polytopes in combinatorial optimization (cites work)
cites work: Lectures on Polytopes

Exponential lower bounds for polytopes in combinatorial optimization (title)
title: Exponential lower bounds for polytopes in combinatorial optimization