CS 789 THEORY SEMINAR [home]

Speaker: Martin Pal
Affiliation: Computer Science, Cornell University
Date: Monday, November 17, 2003
Title: http:  Approximation Via Cost-Sharing: A Simple Approximation
Algorithm for the Multicommodity Rent-or-Buy Problem

Abstract:

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. (FOCS '02); however, this algorithm and its
analysis are both quite complicated, and its performance guarantee is
extremely large.

In this talk, I will show a 8-approximation algorithm for this problem.
The algorithm is conceptually very simple: it picks a random subset of
the source-sink pairs, buys a set of edges spanning these chosen
pairs, and greedily rents paths for the other source-sink pairs.
Moreover, our approximation ratio is by far the best known for any
network design problem with economies of scale, other than special
cases of the rent-or-buy 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---that
ideas from cost sharing can be fruitfully applied in the design and
analysis of approximation algorithms.

This is joint work with Anupam Gupta, Amit Kumar and Tim Roughgarden