On the hardness of approximating Multicut and Sparsest-Cut
From MaRDI portal
Publication:2458939
DOI10.1007/s00037-006-0210-9zbMath1132.68418OpenAlexW2161719898MaRDI QIDQ2458939
Yuval Rabani, Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, D. Sivakumar
Publication date: 5 November 2007
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-006-0210-9
Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Bounds on 2-query locally testable codes with affine tests, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, A note on unique games, Column subset selection problem is UG-hard, Vertical perimeter versus horizontal perimeter, Partial multicuts in trees, A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time, Improved approximation of linear threshold functions, The multi-multiway cut problem, Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds, Mean isoperimetry with control on outliers: exact and approximation algorithms, Pseudorandom sets in Grassmann graph have near-perfect expansion, Approximating maximum integral multiflows on bounded genus graphs, A polyhedral study of lifted multicuts, Approximation and hardness results for label cut and related problems, Expander graphs and their applications, Mathematics of computation through the lens of linear equations and lattices, A unified approach to approximating partial covering problems, Multicut Is FPT, Spectral algorithms for unique games, Affine reductions for LPs and SDPs, Multi-way sparsest cut problem on trees with a control on the number of parts and outliers, Finding the closest ultrametric, A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, On the complexity of the multicut problem in bounded tree-width graphs and digraphs, Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Maximally stable Gaussian partitions with discrete applications, Most balanced minimum cuts, Noise stability of functions with low influences: invariance and optimality, The checkpoint problem, Computational topology and the Unique Games Conjecture, On the hardness of finding near-optimal multicuts in directed acyclic graphs, Unnamed Item, Unnamed Item, Constant ratio fixed-parameter approximation of the edge multicut problem, Inoculation strategies for victims of viruses and the sum-of-squares partition problem, LP-based pivoting algorithm for higher-order correlation clustering, Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth, Quasimetric embeddings and their applications, Strong reductions for extended formulations, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, Path hitting in acyclic graphs, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1, New results on planar and directed multicuts, Unnamed Item
