Approximation Limits of Linear Programs (Beyond Hierarchies)
From MaRDI portal
Publication:3449458
DOI10.1287/MOOR.2014.0694zbMATH Open1343.68308arXiv1204.0957OpenAlexW2150285483MaRDI QIDQ3449458FDOQ3449458
Authors: Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer 
Publication date: 4 November 2015
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Abstract: We develop a framework for approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^{1/2-eps})-approximations for CLIQUE require linear programs of size 2^{n^Omega(eps)}. (This lower bound applies to linear programs using a certain encoding of CLIQUE as a linear optimization problem.) Moreover, we establish a similar result for approximations of semidefinite programs by linear programs. Our main ingredient is a quantitative improvement of Razborov's rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of certain perturbations of the unique disjointness matrix.
Full work available at URL: https://arxiv.org/abs/1204.0957
Recommendations
- Publication:4952591
- Approximation Schemes for Infinite Linear Programs
- A note on approximate linear programming
- scientific article; zbMATH DE number 1217739
- A subexponential bound for linear programming
- On the Complexity of Solving Feasible Linear Programs Specified with Approximate Data
- An Approximation Approach for Linear Programming in Measure Space
- On the probabilistic complexity of finding an approximate solution for linear programming
- Rigorous Lower and Upper Bounds in Linear Programming
Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Computing a nonnegative matrix factorization -- provably
- Expressing combinatorial optimization problems by linear programs
- On the geometric interpretation of the nonnegative rank
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Linear vs. semidefinite extended formulations
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- The Traveling-Salesman Problem and Minimum Spanning Trees
- On Polyhedral Approximations of the Second-Order Cone
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Expander flows, geometric embeddings and graph partitioning
- Geometry of cuts and metrics
- The Probabilistic Communication Complexity of Set Intersection
- Lifts of Convex Sets and Cone Factorizations
- Worst-case results for positive semidefinite rank
- On the power of unique 2-prover 1-round games
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- The Matching Polytope has Exponential Extension Complexity
- Approximate formulations for 0-1 knapsack sets
- An information statistics approach to data stream and communication complexity
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Common information and unique disjointness
- Title not available (Why is that?)
- Integrality gaps for Sherali-Adams relaxations
- An information complexity approach to extended formulations
- Improving integrality gaps via Chvátal-Gomory rounding
- Heuristic analysis, linear programming and branch and bound
- On the distributional complexity of disjointness
- Iterative methods in combinatorial optimization.
- Approximate extended formulations
- On the matrix-cut rank of polyhedra.
- Hypercontractivity, sum-of-squares proofs, and their applications
- Local global tradeoffs in metric embeddings
- Making the Long Code Shorter
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- Compacting cuts. A new linear formulation for minimum cut
Cited In (37)
- Strong reductions for extended formulations
- Information-theoretic approximations of the nonnegative rank
- A framework for solving mixed-integer semidefinite programs
- Logic Programming and Nonmonotonic Reasoning
- Approximating nonnegative polynomials via spectral sparsification
- Euclidean distance matrices and separations in communication complexity theory
- A note on the extension complexity of the knapsack polytope
- A characterization of Delsarte's linear programming bound as a ratio bound
- Exponential lower bounds for polytopes in combinatorial optimization
- A guide to conic optimisation and its applications
- Worst-case results for positive semidefinite rank
- Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs
- A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Common information and unique disjointness
- On polyhedral and second-order cone decompositions of semidefinite optimization problems
- Title not available (Why is that?)
- Tighter bounds on transient moments of stochastic chemical systems
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Uncapacitated flow-based extended formulations
- A Polyhedral Characterization of Border Bases
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Title not available (Why is that?)
- Parameterized extension complexity of independent set and related problems
- The matching problem has no small symmetric SDP
- Average case polyhedral complexity of the maximum stable set problem
- Extension complexity of formal languages
- An almost optimal algorithm for computing nonnegative rank
- Extended formulations for radial cones
- New limits of treewidth-based tractability in optimization
- Worst-case analysis of clique MIPs
- Polynomial size linear programs for problems in \textsc{P}
- Approximate cone factorizations and lifts of polytopes
- Inapproximability of combinatorial problems via small LPs and SDPs
- Affine reductions for LPs and SDPs
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
This page was built for publication: Approximation Limits of Linear Programs (Beyond Hierarchies)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449458)
