On the Integrality Gap of a Natural Formulation of the Single-sin.pdf.pdf' (253.77 kB)
On the Integrality Gap of a Natural Formulation of the Single-sink Buy-at-Bulk Network Design Problem
journal contributionposted on 1980-05-01, 00:00 authored by Naveen Garg, Rohit Khandekar, Goran Konjevod, Ramamoorthi RaviRamamoorthi Ravi, F. S. Salman, Amitabh Sinha
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.