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
- 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
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)- Approximate cone factorizations and lifts of polytopes
- A characterization of Delsarte's linear programming bound as a ratio bound
- A Polyhedral Characterization of Border Bases
- Euclidean distance matrices and separations in communication complexity theory
- Inapproximability of combinatorial problems via small LPs and SDPs
- New limits of treewidth-based tractability in optimization
- Tighter bounds on transient moments of stochastic chemical systems
- Average case polyhedral complexity of the maximum stable set problem
- A note on the extension complexity of the knapsack polytope
- scientific article; zbMATH DE number 872648 (Why is no real title available?)
- Extension complexity of formal languages
- A guide to conic optimisation and its applications
- Worst-case analysis of clique MIPs
- Information-theoretic approximations of the nonnegative rank
- Exponential lower bounds for polytopes in combinatorial optimization
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Uncapacitated flow-based extended formulations
- A framework for solving mixed-integer semidefinite programs
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- Parameterized extension complexity of independent set and related problems
- Affine reductions for LPs and SDPs
- Worst-case results for positive semidefinite rank
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- The matching problem has no small symmetric SDP
- Polynomial size linear programs for problems in \textsc{P}
- An almost optimal algorithm for computing nonnegative rank
- Approximating nonnegative polynomials via spectral sparsification
- Extension complexity, MSO logic, and treewidth
- Logic Programming and Nonmonotonic Reasoning
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- Extended formulations for radial cones
- On polyhedral and second-order cone decompositions of semidefinite optimization problems
- 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
- Common information and unique disjointness
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)
