TY - GEN

T1 - Approximation via cost-sharing

T2 - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003

AU - Gupta, A.

AU - Kumar, A.

AU - Pál, M.

AU - Roughgarden, T.

N1 - Publisher Copyright:
© 2003 IEEE.

PY - 2003

Y1 - 2003

N2 - We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. The first constant-factor approximation algorithm for this problem was recently given by Kumar et al.; however, this algorithm and its analysis are both quite complicated, and its performance guarantee is extremely large. In this paper, we give a conceptually simple 12-approximation algorithm for this problem. Our analysis of this algorithm makes crucial use of cost sharing, the task of allocating the cost of an object to many users of the object in a "fair" manner. While techniques from approximation algorithms have recently yielded new progress on cost sharing problems, our work is the first to show the converse - those ideas from cost sharing can be fruitfully applied in the design and analysis of approximation algorithms.

AB - We study the multicommodity rent-or-buy problem, a type of network design problem with economies of scale. In this problem, capacity on an edge can be rented, with cost incurred on a per-unit of capacity basis, or bought, which allows unlimited use after payment of a large fixed cost. Given a graph and a set of source-sink pairs, we seek a minimum-cost way of installing sufficient capacity on edges so that a prescribed amount of flow can be sent simultaneously from each source to the corresponding sink. The first constant-factor approximation algorithm for this problem was recently given by Kumar et al.; however, this algorithm and its analysis are both quite complicated, and its performance guarantee is extremely large. In this paper, we give a conceptually simple 12-approximation algorithm for this problem. Our analysis of this algorithm makes crucial use of cost sharing, the task of allocating the cost of an object to many users of the object in a "fair" manner. While techniques from approximation algorithms have recently yielded new progress on cost sharing problems, our work is the first to show the converse - those ideas from cost sharing can be fruitfully applied in the design and analysis of approximation algorithms.

KW - Algorithm design and analysis

KW - Approximation algorithms

KW - Chromium

KW - Computer science

KW - Cost function

KW - Economies of scale

KW - Performance analysis

UR - http://www.scopus.com/inward/record.url?scp=20744432095&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=20744432095&partnerID=8YFLogxK

U2 - 10.1109/SFCS.2003.1238233

DO - 10.1109/SFCS.2003.1238233

M3 - Conference contribution

AN - SCOPUS:20744432095

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 606

EP - 615

BT - Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003

PB - IEEE Computer Society

Y2 - 11 October 2003 through 14 October 2003

ER -