Submodular Cost Allocation Problem and Applications
From MaRDI portal
Publication:3012819
DOI10.1007/978-3-642-22006-7_30zbMath1333.90092arXiv1105.2040OpenAlexW1695878779MaRDI QIDQ3012819
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1105.2040
Programming involving graphs or networks (90C35) Convex programming (90C25) Hypergraphs (05C65) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Related Items
Improved Approximation Algorithms for Inventory Problems, \(\ell_p\)-norm multiway cut, Sperner’s Colorings and Optimal Partitioning of the Simplex, Approximation algorithms for connected maximum cut and related problems, Multicommodity flows and cuts in polymatroidal networks, Approximation algorithms for vertex happiness, New approximations and hardness results for submodular partitioning problems
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
- Fast approximate energy minimization with label costs
- Finding minimum 3-way cuts in hypergraphs
- Minimizing symmetric submodular functions
- An improved approximation algorithm of MULTIWAY CUT.
- Greedy splitting algorithms for approximating multiway partition problems
- Rounding algorithms for a geometric embedding of minimum multiway cut
- The Design of Approximation Algorithms
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- Approximation algorithms for classification problems with pairwise relationships
- Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings
- Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
- The Complexity of Multiterminal Cuts
- Multiway cuts in node weighted graphs
- Submodular Function Minimization under Covering Constraints
- Symmetry and Approximability of Submodular Maximization Problems
- Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Approximation Algorithms for Submodular Multiway Partition
- Cutsets and partitions of hypergraphs
- Facility location with hierarchical facility costs
