Optimal Bounds for the k -cut Problem

DOI10.1145/3478018MaRDI QIDQ5066939zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, David G. Harris, Euiwoong Lee, Jason Li

Publication date 31 March 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3478018

zbMATH Keywords

\(k\)-cutcontraction algorithm

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• New bounds for the maximum cut problem
• On the \(k\)-cut problem
• An optimal space lower bound for approximating MAX-CUT
• Fast and Deterministic Approximations for k-Cut.
• Fast and deterministic approximations for \(k\)-cut
• On the approximability of Max-Cut
• Approximation algorithms for minimum \(K\)-cut
• A class of spectral bounds for max \(k\)-cut
• The number of minimum k-cuts: improving the Karger-Stein bound
• Approximation and intractability results for the maximum cut problem and its variants

Cited in

(7)

• Theoretical lower bound for border length minimization problem
• Optimality proof of the Kise-Ibaraki-Mine algorithm
• scientific article; zbMATH DE number 1420913 (Why is no real title available?)
• Breaking the n ^k barrier for minimum k -cut on simple graphs
• Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Algorithms for the ferromagnetic Potts model on expanders

This page was built for publication: Optimal Bounds for the k -cut Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066939)