A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem

We present the first constant factor approximation algorithm for network design with multiple commodities and economies of scale. We consider the rent-or-buy problem, a type of multicommodity buy-at-bulk network design in which there are two ways to install capacity on any given edge. Capacity 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. Recent work on buy-at-bulk network design has concentrated on the special case where all sinks are identical; existing constant factor approximation algorithms for this special case make crucial use of the assumption that all commodities ship flow to the same sink vertex and do not obviously extend to the multicommodity rent-or-buy problem. Prior to our work, the best heuristics for the multicommodity rent-or-buy problem achieved only logarithmic performance guarantees and relied on the machinery of relaxed metrical task systems or of metric embeddings. By contrast, we solve the network design problem directly via a novel primal-dual algorithm.

Authors

• Amit Kumar 0001
• Anupam Gupta 0001
• Tim Roughgarden

Keywords

• Approximation algorithms
• Algorithm design and analysis
• Economies of scale
• Cost function
• Piecewise linear approximation
• Piecewise linear techniques
• Marine vehicles
• Machinery
• Computer science
• Estimation Algorithm
• Constant Factor
• Constant-factor Approximation Algorithm
• Network Design
• Performance Guarantees
• Use Of Assumptions
• Primal-dual Algorithm
• Network Design Problem
• Undirected
• Shortest Path
• Feasible Solution
• Local Facilities
• Algorithm For Problem
• Incremental Cost
• Concave Function
• Interior Point Method
• Piecewise Linear Function
• Beginning Of Stage
• Operation Of Facilities
• Cost Of Solution
• Dual Variables
• Set Of Demands
• Dual Solution
• Facility Location Problem
• Facilities In Settings
• Integer Programming Formulation
• Amount Of Capacity
• Rightmost Point
• Edge Path