Monotone submodular multiway partition

DOI10.1007/978-3-031-93112-3_6MaRDI QIDQ6880148zbMATH OpenFDO

Authors Richard Bi, Karthekeyan Chandrasekaran, Soham Joshi

Publication date 22 December 2025

Full work available at URL https://doi.org/10.1007/978-3-031-93112-3_6

zbMATH Keywords

approximation algorithmsmonotone submodular functionsmultiway partition

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Cites work

• A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut
• An improved approximation algorithm of MULTIWAY CUT.
• An improved integrality gap for the Călinescu-Karloff-Rabani relaxation for multiway cut
• Approximation Algorithms for Submodular Multiway Partition
• From query complexity to computational complexity
• Greedy splitting algorithms for approximating multiway partition problems
• scientific article; zbMATH DE number 5485510 (Why is no real title available?)
• Improving the integrality gap for multiway cut
• Local distribution and the symmetry gap: approximability of multiway partitioning problems
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Optimal 3-terminal cuts and linear programming
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Rounding algorithms for a geometric embedding of minimum multiway cut.
• Simplex partitioning via exponential clocks and the multiway cut problem
• Symmetry and approximability of submodular maximization problems
• The Complexity of Multiterminal Cuts

Cited in

(1)

• Approximating submodular matroid-constrained partitioning

This page was built for publication: Monotone submodular multiway partition

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