Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
On the Integrality Gap of a Natural Formulation of the Single-sink Buy-at-Bulk Network Design Problem
| |
|
On the Integrality Gap of a Natural Formulation of the Single-sink Buy-at-Bulk Network Design Problem
Naveen Garg6 , Rohit Khandekar6 , Goran Konjevod7 , R. Ravi8 , F. S. Salman9 and Amitabh Sinha8 
| (6) |
Department of Computer Science and Engineering, Indian Institute of Technology, New Delhi, India |
| (7) |
Department of Computer Science and Engineering, Arizona State University, Tempe AZ 85287, USA |
| (8) |
GSIA, Carnegie Mellon University, Pittsburgh, PA 15213-3890, USA |
| (9) |
Krannert School of Management, Purdue University, West Lafayette IN 47907, USA |
Abstract
We study two versions of the single sink buy-at-bulk network design problem. We are given a network and a single sink, and
several sources which demand a certain amount of flow to be routed to the sink. We are also given a finite set of cable types
which have different cost characteristics and obey the principle of economies of scale. We wish to construct a minimum cost
network to support the demands, using our given cable types. We study a natural integer program formulation of the problem,
and show that its integrality gap is O(k), where k is the number of cable types. As a consequence, we also provide an O(k)-approximation algorithm.
This research was supported by a faculty development grant awarded to R. Ravi by the Carnegie Bosch Institute, Carnegie Mellon
University, Pittsburgh PA 15213-3890.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|