Inapproximability of Combinatorial Problems via Small LPs and SDPs

DOI10.1145/2746539.2746550zbMath1321.90098OpenAlexW2077658979MaRDI QIDQ2941494

Daniel Zink, Gábor Braun, Sebastian Pokutta

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

polyhedral approximationstable setsrestrictionsextended formulations

Mathematics Subject Classification ID

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

Related Items (9)

Average case polyhedral complexity of the maximum stable set problem ⋮ 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 ⋮ A Polyhedral Characterization of Border Bases ⋮ Strong reductions for extended formulations ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ

Uses Software

• Graphs

Cites Work

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

This page was built for publication: Inapproximability of Combinatorial Problems via Small LPs and SDPs