Approximating submodular matroid-constrained partitioning

DOI10.1016/J.TCS.2026.115881MaRDI QIDQ7229631zbMATH OpenFDO

Authors Kristóf Bérczi, Tamás Király, Daniel P. Szabo, Karthekeyan Chandrasekaran

Publication date 16 April 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115881

zbMATH Keywords

approximation algorithmsmultiway cutmatroid constraintssubmodular partitioning

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Approximating submodular \(k\)-partition via principal partition sequence
• Approximation Algorithms for Submodular Multiway Partition
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Finding k Cuts within Twice the Optimal
• Greedy splitting algorithms for approximating multiway partition problems
• Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
• Lattice Theory of Generalized Partitions
• Minimizing submodular functions over families of sets
• Monotone submodular multiway partition
• Multiway cut, pairwise realizable distributions, and descending thresholds
• New approximations and hardness results for submodular partitioning problems
• On minimum 3-cuts and approximating k-cuts using cut trees
• On the hardness of approximating the \(k\)-\textsc{Way Hypergraph Cut} problem
• The Complexity of Multiterminal Cuts
• The Steiner k-Cut Problem
• The polymatroid Steiner problems

This page was built for publication: Approximating submodular matroid-constrained partitioning

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