The matching polytope does not admit fully-polynomial size relaxation schemes

DOI10.1137/1.9781611973730.57zbMath1372.68251arXiv1403.6710OpenAlexW2134443705MaRDI QIDQ5362994

Gábor Braun, Sebastian Pokutta

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.6710

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

Query Complexity in Expectation ⋮ Common information and unique disjointness ⋮ Average case polyhedral complexity of the maximum stable set problem ⋮ The matching problem has no small symmetric SDP ⋮ The Frank-Wolfe algorithm: a short introduction ⋮ Extension Complexity of Independent Set Polytopes ⋮ Affine reductions for LPs and SDPs ⋮ Approximating Nonnegative Polynomials via Spectral Sparsification ⋮ On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space ⋮ Extended formulations for vertex cover

This page was built for publication: The matching polytope does not admit fully-polynomial size relaxation schemes