Approximation Limits of Linear Programs (Beyond Hierarchies)
From MaRDI portal
Publication:3449458
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)
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.
Recommendations
- scientific article; zbMATH DE number 1445278
- 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
Cites work
- Title not available (Why is no real title available?)
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- An information complexity approach to extended formulations
- An information statistics approach to data stream and communication complexity
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximate extended formulations
- Approximate formulations for 0-1 knapsack sets
- Common information and unique disjointness
- Computing a nonnegative matrix factorization -- provably
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Expander flows, geometric embeddings and graph partitioning
- Expressing combinatorial optimization problems by linear programs
- Geometry of cuts and metrics
- Heuristic analysis, linear programming and branch and bound
- Hypercontractivity, sum-of-squares proofs, and their applications
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improving integrality gaps via Chvátal-Gomory rounding
- Integrality gaps for Sherali-Adams relaxations
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Iterative methods in combinatorial optimization.
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- Lifts of Convex Sets and Cone Factorizations
- Linear vs. semidefinite extended formulations
- Local global tradeoffs in metric embeddings
- Making the Long Code Shorter
- On Polyhedral Approximations of the Second-Order Cone
- On the distributional complexity of disjointness
- On the geometric interpretation of the nonnegative rank
- On the matrix-cut rank of polyhedra.
- On the power of unique 2-prover 1-round games
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- The Probabilistic Communication Complexity of Set Intersection
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Worst-case results for positive semidefinite rank
Cited in
(36)- Information-theoretic approximations of the nonnegative rank
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- A framework for solving mixed-integer semidefinite programs
- Logic Programming and Nonmonotonic Reasoning
- Euclidean distance matrices and separations in communication complexity theory
- Approximating nonnegative polynomials via spectral sparsification
- 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
- Worst-case results for positive semidefinite rank
- A guide to conic optimisation and its applications
- A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
- 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
- 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
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- A Polyhedral Characterization of Border Bases
- The matching problem has no small symmetric SDP
- Parameterized extension complexity of independent set and related problems
- scientific article; zbMATH DE number 872648 (Why is no real title available?)
- Average case polyhedral complexity of the maximum stable set problem
- Extension complexity of formal languages
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- Extended formulations for radial cones
- New limits of treewidth-based tractability in optimization
- An almost optimal algorithm for computing nonnegative rank
- Extension complexity, MSO logic, and treewidth
- 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
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)
