Approximation Limits of Linear Programs (Beyond Hierarchies)
From MaRDI portal
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Linear programming (90C05) Semidefinite programming (90C22) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)
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
- 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
- Compacting cuts. A new linear formulation for minimum cut
- 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
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- 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
(43)- The matching problem has no small symmetric SDP
- Affine reductions for LPs and SDPs
- Euclidean distance matrices and separations in communication complexity theory
- Information-theoretic approximations of the nonnegative rank
- Worst-case analysis of clique MIPs
- New limits of treewidth-based tractability in optimization
- Extended formulations for radial cones
- On polyhedral and second-order cone decompositions of semidefinite optimization problems
- A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
- Polynomial size linear programs for problems in \textsc{P}
- Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
- Approximate cone factorizations and lifts of polytopes
- Parameterized extension complexity of independent set and related problems
- A note on the extension complexity of the knapsack polytope
- Exponential lower bounds for polytopes in combinatorial optimization
- Inapproximability of combinatorial problems via small LPs and SDPs
- Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
- Extension complexity, MSO logic, and treewidth
- Common information and unique disjointness
- Average case polyhedral complexity of the maximum stable set problem
- Approximating nonnegative polynomials via spectral sparsification
- A guide to conic optimisation and its applications
- A framework for solving mixed-integer semidefinite programs
- scientific article; zbMATH DE number 872648 (Why is no real title available?)
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
- Logic Programming and Nonmonotonic Reasoning
- An almost optimal algorithm for computing nonnegative rank
- A Polyhedral Characterization of Border Bases
- Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks
- Tighter bounds on transient moments of stochastic chemical systems
- Hard submatrices for nonnegative rank and communication complexity
- Hard submatrices for non-negative rank and communication complexity
- Instance-specific linear relaxations of semidefinite optimization problems
- Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
- A note on the maximum clique LP relaxation
- Lower bounds on the complexity of mixed-integer programs for stable set and knapsack
- Determining inscribability of polytopes via rank minimization based on slack matrices
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Uncapacitated flow-based extended formulations
- Worst-case results for positive semidefinite rank
- Extension complexity of formal languages
- A characterization of Delsarte's linear programming bound as a ratio bound
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)
