Submodular Cost Allocation Problem and Applications

DOI10.1007/978-3-642-22006-7_30MaRDI QIDQ3012819zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Alina Ene

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

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Approximation algorithms (68W25) Hypergraphs (05C65)

Abstract: We study the Minimum Submodular-Cost Allocation problem (MSCA). In this problem we are given a finite ground set $V$ and $k$ non-negative submodular set functions $f_1,\mathrm{...},f_k$ on $V$. The objective is to partition $V$ into $k$ (possibly empty) sets $A_1,\mathrm{...},A_k$ such that the sum $su{m}_{i=1}^k{f}_i(A_i)$ is minimized. Several well-studied problems such as the non-metric facility location problem, multiway-cut in graphs and hypergraphs, and uniform metric labeling and its generalizations can be shown to be special cases of MSCA. In this paper we consider a convex-programming relaxation obtained via the Lov'asz-extension for submodular functions. This allows us to understand several previous relaxations and rounding procedures in a unified fashion and also develop new formulations and approximation algorithms for several problems. In particular, we give a $(1.5-1/k)$-approximation for the hypergraph multiway partition problem. We also give a $min2(1-1/k),H_{Delta}$-approximation for the hypergraph multiway cut problem when $Delta$ is the maximum hyperedge size. Both problems generalize the multiway cut problem in graphs and the hypergraph cut problem is approximation equivalent to the node-weighted multiway cut problem in graphs.

Recommendations

• scientific article; zbMATH DE number 3922372
• Submodular functions: optimization and approximation
• Practical budgeted submodular maximization
• scientific article; zbMATH DE number 446490
• Submodular functions and optimization
• An application of submodular flows
• Submodular optimization problems and greedy strategies: a survey
• Submodular Optimization with Contention Resolution Extensions.
• Submodular optimization views on the random assignment problem
• Submodular flow problem with a nonseparable cost function

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.
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• Approximation Algorithms for Submodular Multiway Partition
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Computing minimum multiway cuts in hypergraphs from hypertree packings
• Cutsets and partitions of hypergraphs
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Facility location with hierarchical facility costs
• Fast approximate energy minimization with label costs
• Finding minimum 3-way cuts in hypergraphs
• Greedy splitting algorithms for approximating multiway partition problems
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Minimizing symmetric submodular functions
• Multiway cuts in node weighted graphs
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Submodular Function Minimization under Covering Constraints
• Symmetry and Approximability of Submodular Maximization Problems
• The Complexity of Multiterminal Cuts
• The design of approximation algorithms

Cited in

(11)

• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• New approximations and hardness results for submodular partitioning problems
• Improved approximation algorithms for inventory problems
• Hardness of submodular cost allocation: lattice matching and a simplex coloring conjecture
• Utility Design for Distributed Resource Allocation—Part II: Applications to Submodular, Covering, and Supermodular Problems
• Application of M-convex submodular flow problem to mathematical economics
• Approximation algorithms for vertex happiness
• Sperner's colorings and optimal partitioning of the simplex
• _p-norm multiway cut
• An o( n)-approximation for submodular facility location
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems

This page was built for publication: Submodular Cost Allocation Problem and Applications

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