\(\ell_p\)-norm multiway cut

DOI10.1007/s00453-022-00983-3OpenAlexW4281386767MaRDI QIDQ2165036

Karthekeyan Chandrasekaran, Weihang Wang

Publication date: 18 August 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsmultiway cut

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized graph separation problems
• An improved approximation algorithm of MULTIWAY CUT.
• Min-max correlation clustering via multicut
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• Local guarantees in graph cuts and clustering
• Optimal 3-terminal cuts and linear programming
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Submodular Cost Allocation Problem and Applications
• Recognizing decomposable graphs
• The Complexity of Multiterminal Cuts
• Simplex Transformations and the Multiway Cut Problem
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Correlation Clustering and Biclustering With Locally Bounded Errors
• Min-Max Graph Partitioning and Small Set Expansion
• Simplex partitioning via exponential clocks and the multiway cut problem
• Improving the integrality gap for multiway cut

This page was built for publication: \(\ell_p\)-norm multiway cut