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.
My Menu
Saved Items

On the Integrality Gap of a Natural Formulation of the Single-sink Buy-at-Bulk Network Design Problem

Naveen GargContact Information, Rohit KhandekarContact Information, Goran KonjevodContact Information, R. RaviContact Information, F. S. SalmanContact Information and Amitabh SinhaContact Information

(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.

Contact Information Naveen Garg
Email: naveen@cse.iitd.ernet.in

Contact Information Rohit Khandekar
Email: rohitkg@cse.iitd.ernet.in

Contact Information Goran Konjevod
Email: goran@asu.edu

Contact Information R. Ravi
Email: ravi@andrew.cmu.edu

Contact Information F. S. Salman
Email: salmanf@mgmt.purdue.edu

Contact Information Amitabh Sinha
Email: asinhag@andrew.cmu.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb18
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)