Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
Authors:
- Gagan GoelGGGagan Goel
- Chinmay KarandeCKChinmay Karande
- Pushkar TripathiPTPushkar Tripathi
- Lei WangLWLei Wang
- 1 October 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 755-764
Abstract
Applications in complex systems such as the Internet have spawned recent interest in studying situations involving multiple agents with their individual cost or utility functions. In this paper, we introduce an algorithmic framework for studying combinatorial problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems (Vertex Cover, Shortest Path, Perfect Matching, and Spanning Tree) in this setting and establish tight upper and lower bounds for the approximability of these problems.Keywords
This publication has 21 references indexed in Scilit:
- Submodular Function Minimization under Covering Constraints2009
- A Simple Combinatorial Algorithm for Submodular Function Minimization2009
- Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions2008
- Vertex cover might be hard to approximate to withinJournal of Computer and System Sciences, 2008
- Inapproximability Results for Combinatorial Auctions with Submodular Utility FunctionsAlgorithmica, 2007
- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization2007
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)2007
- On the hardness of approximating vertex coverAnnals of Mathematics, 2005
- The Communication Complexity of Approximate Set Packing and Covering2002
- A combinatorial strongly polynomial algorithm for minimizing submodular functionsJournal of the ACM, 2001