Approximation Algorithms for Submodular Multiway Partition

DOI10.1109/FOCS.2011.34MaRDI QIDQ5495000zbMATH OpenFDO

Authors Chandra Chekuri, Alina Ene

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.34

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cited in

(16)

• Computing minimum multiway cuts in hypergraphs
• New approximations and hardness results for submodular partitioning problems
• Mixed-case community detection problem in social networks: algorithms and analysis
• Hypergraph \(k\)-cut in randomized polynomial time
• Approximation algorithms for vertex happiness
• An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
• Submodular Cost Allocation Problem and Applications
• Improved approximation algorithms for inventory problems
• Constrained submodular maximization via a nonsymmetric technique
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• Posimodular function optimization
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• An o( n)-approximation for submodular facility location
• Monotone submodular multiway partition
• Submodular combinatorial information measures with applications in machine learning
• Approximating submodular matroid-constrained partitioning

This page was built for publication: Approximation Algorithms for Submodular Multiway Partition

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