Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Approximability of combinatorial problems with multi-agent submodular cost functions

Approximability of combinatorial problems with multi-agent submodular cost functions Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions GAGAN GOEL, CHINMAY KARANDE, PUSHKAR TRIPATHI and LEI WANG Georgia Institute of Technology Applications in complex systems such as the Internet have spawned a 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 optimization problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems in this framework and establish upper and lower bounds on their approximability. Categories and Subject Descriptors: F.2.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity General Terms: Theory, Economics, Algorithms, Design Additional Key Words and Phrases: Submodular Functions, Combinatorial Optimization 1. INTRODUCTION A multitude of fundamental computational problems with real-world applications can be cast in the following framework: We are given a set X of elements, a collection C of subsets of X (i.e. C † 2X ) and a cost function f over the subsets of X. The collection C is typically speci ed via a combinatorial structure like a matroid or a graph property (for instance, the set of all spanning trees in a graph). The objective is http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

Approximability of combinatorial problems with multi-agent submodular cost functions

Download PDF
4 pages

Loading next page...
 
/lp/association-for-computing-machinery/approximability-of-combinatorial-problems-with-multi-agent-submodular-t9tFDvdE7X
Publisher
Association for Computing Machinery
Copyright
Copyright © 2010 by ACM Inc.
ISSN
1551-9031
DOI
10.1145/1980534.1980542
Publisher site
See Article on Publisher Site

Abstract

Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions GAGAN GOEL, CHINMAY KARANDE, PUSHKAR TRIPATHI and LEI WANG Georgia Institute of Technology Applications in complex systems such as the Internet have spawned a 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 optimization problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems in this framework and establish upper and lower bounds on their approximability. Categories and Subject Descriptors: F.2.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity General Terms: Theory, Economics, Algorithms, Design Additional Key Words and Phrases: Submodular Functions, Combinatorial Optimization 1. INTRODUCTION A multitude of fundamental computational problems with real-world applications can be cast in the following framework: We are given a set X of elements, a collection C of subsets of X (i.e. C † 2X ) and a cost function f over the subsets of X. The collection C is typically speci ed via a combinatorial structure like a matroid or a graph property (for instance, the set of all spanning trees in a graph). The objective is

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Jun 1, 2010

There are no references for this article.