Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
From MaRDI portal
Publication:5741731
DOI10.1137/1.9781611973105.23zbMath1421.68217arXiv1503.03905OpenAlexW2950135040MaRDI QIDQ5741731
Publication date: 15 May 2019
Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.03905
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (14)
The Complexity of General-Valued CSPs ⋮ The Limitations of Optimization from Samples ⋮ Improved Approximation Algorithms for Inventory Problems ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Sperner’s Colorings and Optimal Partitioning of the Simplex ⋮ A tight \(\sqrt{2} \)-approximation for linear 3-cut ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ Unnamed Item ⋮ Approximation algorithms for vertex happiness ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time ⋮ New approximations and hardness results for submodular partitioning problems
This page was built for publication: Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
