We study the {\em multicommodity rent-or-buy problem}, a type of
network design problem with economies of scale. In this problem,
capacity on an edge can be {\em rented}, with cost incurred on a
per-unit of capacity basis, or {\em 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 paper, we give a conceptually simple 12-approximation
algorithm for this problem. Our analysis of this algorithm makes
crucial use of {\em 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.