Inapproximability of combinatorial problems via small LPs and SDPs

DOI10.1145/2746539.2746550MaRDI QIDQ2941494zbMATH OpenOpenAlexFDO

Authors Gábor Braun, Sebastian Pokutta, Daniel Zink

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2746539.2746550

zbMATH Keywords

extended formulationspolyhedral approximationrestrictionsstable sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Combinatorial optimization (90C27)

Recommendations

• Affine reductions for LPs and SDPs
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximation Limits of Linear Programs (Beyond Hierarchies)

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(12)

• The matching problem has no small symmetric SDP
• Affine reductions for LPs and SDPs
• Limitations of semidefinite programs for separable states and entangled games
• Information-theoretic approximations of the nonnegative rank
• Average case polyhedral complexity of the maximum stable set problem
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• On LP-based approximability for strict CSPs
• A Polyhedral Characterization of Border Bases
• A tight approximation algorithm for the cluster vertex deletion problem
• Approximate graph colouring and the hollow shadow
• Approximate graph coloring and the crystal with a hollow shadow

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Inapproximability of combinatorial problems via small LPs and SDPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941494)