Approximation Algorithms for Submodular Multiway Partition

DOI10.1109/FOCS.2011.34zbMATH Open1292.68163MaRDI QIDQ5495000FDOQ5495000

Alina Ene, Chandra Chekuri

Publication date: 30 July 2014

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

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cited In (13)

• 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
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Multicommodity flows and cuts in polymatroidal networks
• Approximation algorithms for vertex happiness
• Posimodular function optimization
• Improved Approximation Algorithms for Inventory Problems
• Computing minimum multiway cuts in hypergraphs
• Submodular Cost Allocation Problem and Applications
• Constrained Submodular Maximization via a Nonsymmetric Technique
• An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

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)