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 (50)
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 ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time ⋮ Strong reductions for extended formulations ⋮ An approximation algorithm for the \(\boldsymbol{K}\)-prize-collecting multicut problem in trees with submodular penalties ⋮ Fitting metrics and ultrametrics with minimum disagreements ⋮ 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
This page was built for publication: On the hardness of approximating Multicut and Sparsest-Cut
