Affine reductions for LPs and SDPs
From MaRDI portal
Publication:1717229
DOI10.1007/s10107-017-1221-9zbMath1410.90147arXiv1410.8816OpenAlexW2964305649MaRDI QIDQ1717229
Sebastian Pokutta, Gábor Braun, Daniel Zink
Publication date: 7 February 2019
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1410.8816
Semidefinite programming (90C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Common information and unique disjointness
- Average case polyhedral complexity of the maximum stable set problem
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Optimization, approximation, and complexity classes
- Expressing combinatorial optimization problems by linear programs
- Parallel approximation algorithms by positive linear programming
- Strong reductions for extended formulations
- Information-theoretic approximations of the nonnegative rank
- A short proof that the extension complexity of the correlation polytope grows exponentially
- Some \(0/1\) polytopes need exponential size extended formulations
- On the hardness of approximating Multicut and Sparsest-Cut
- The Approximability of Constraint Satisfaction Problems
- New Inapproximability Bounds for TSP
- Inapproximability of Combinatorial Problems via Small LPs and SDPs
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Average Case Polyhedral Complexity of the Maximum Stable Set Problem
- Improved approximation of Max-Cut on graphs of bounded degree
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- How Good is the Goemans--Williamson MAX CUT Algorithm?
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- The matching problem has no small symmetric SDP
- Extension Complexity of Independent Set Polytopes
- The Matching Polytope has Exponential Extension Complexity
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Lifts of Convex Sets and Cone Factorizations
- Integrality gaps for Sherali-Adams relaxations
- CSP gaps and reductions in the lasserre hierarchy
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
- Mathematical Foundations of Computer Science 2004
- The matching polytope does not admit fully-polynomial size relaxation schemes
- Linear vs. semidefinite extended formulations
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- An information complexity approach to extended formulations
- Approximation resistance from pairwise independent subgroups
This page was built for publication: Affine reductions for LPs and SDPs
