Approximation Limits of Linear Programs (Beyond Hierarchies)
From MaRDI portal
Publication:3449458
DOI10.1287/moor.2014.0694zbMath1343.68308arXiv1204.0957OpenAlexW2150285483MaRDI QIDQ3449458
David Steurer, Samuel Fiorini, Gábor Braun, Sebastian Pokutta
Publication date: 4 November 2015
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.0957
Semidefinite programming (90C22) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (33)
Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ Common information and unique disjointness ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ The matching problem has no small symmetric SDP ⋮ Parameterized extension complexity of independent set and related problems ⋮ Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks ⋮ Tighter bounds on transient moments of stochastic chemical systems ⋮ Unnamed Item ⋮ Affine reductions for LPs and SDPs ⋮ A note on the extension complexity of the knapsack polytope ⋮ Approximating Nonnegative Polynomials via Spectral Sparsification ⋮ Euclidean distance matrices and separations in communication complexity theory ⋮ A guide to conic optimisation and its applications ⋮ A framework for solving mixed-integer semidefinite programs ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Information-theoretic approximations of the nonnegative rank ⋮ A Polyhedral Characterization of Border Bases ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Strong reductions for extended formulations ⋮ Extended formulations for radial cones ⋮ On polyhedral and second-order cone decompositions of semidefinite optimization problems ⋮ On the existence of 0/1 polytopes with high semidefinite extension complexity ⋮ Uncapacitated flow-based extended formulations ⋮ Worst-case results for positive semidefinite rank ⋮ A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Polynomial size linear programs for problems in \textsc{P} ⋮ Extension complexity of formal languages ⋮ Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs ⋮ Lower bounds on matrix factorization ranks via noncommutative polynomial optimization ⋮ Worst-case analysis of clique MIPs ⋮ Approximate cone factorizations and lifts of polytopes ⋮ New limits of treewidth-based tractability in optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Common information and unique disjointness
- An information statistics approach to data stream and communication complexity
- Worst-case results for positive semidefinite rank
- Approximate formulations for 0-1 knapsack sets
- Expressing combinatorial optimization problems by linear programs
- On the distributional complexity of disjointness
- On the geometric interpretation of the nonnegative rank
- Approximate extended formulations
- On the Matrix-Cut Rank of Polyhedra
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- Local Global Tradeoffs in Metric Embeddings
- Iterative Methods in Combinatorial Optimization
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Making the Long Code Shorter
- On the power of unique 2-prover 1-round games
- Improving Integrality Gaps via Chvátal-Gomory Rounding
- Heuristic analysis, linear programming and branch and bound
- Cones of Matrices and Set-Functions and 0–1 Optimization
- The Probabilistic Communication Complexity of Set Intersection
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- The Matching Polytope has Exponential Extension Complexity
- Lifts of Convex Sets and Cone Factorizations
- Integrality gaps for Sherali-Adams relaxations
- Linear vs. semidefinite extended formulations
- Computing a nonnegative matrix factorization -- provably
- Hypercontractivity, sum-of-squares proofs, and their applications
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- An information complexity approach to extended formulations
- 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
This page was built for publication: Approximation Limits of Linear Programs (Beyond Hierarchies)
