Paper Info
Title
Improved approximation algorithms for the single-sink buy-at-bulk network design problems
Abstract
Consider a given undirected graph G=(V,E) with non-negative edge lengths, a root node r@?V, and a set D@?V of demands with d"v representing the units of flow that demand v@?D wishes to send to the root. We are also given K types of cables, each with a specified capacity and cost per unit length. The single-sink buy-at-bulk (SSBB) problem asks for a low-cost installation of cables along the edges of G, such that the demands can simultaneously send their flow to root r. The problem is studied with and without the restriction that the flow from a node must follow a single path to the root. We are allowed to install zero or more copies of a cable type on each edge. The SSBB problem is NP-hard. In this paper, we present a 153.6-approximation algorithm for the SSBB problem improving the previous best ratio of 216. For the case in which the flow is splittable, we improve the previous best ratio of 76.8 to @a"K, where @a"K is less than 67.94 for all K. In particular, @a"2
Year
DOI
Venue
2009
10.1016/j.jda.2008.12.003
Journal of Discrete Algorithms
Keywords
Field
DocType
approximation algorithms,demand v,root node,improved approximation algorithm,single-sink buy-at-bulk,cable type,low-cost installation,network design,k type,combinatorial optimization,randomized algorithms,non-negative edge length,ssbb problem,single path,previous best ratio,set d,single-sink buy-at-bulk network design
Approximation algorithm,Graph,Discrete mathematics,Combinatorics,Algorithmics,Network planning and design,Sink (computing),Mathematics,Distributed computing
Journal
Volume
Issue
ISSN
7
2
Journal of Discrete Algorithms
Citations 
PageRank 
References 
18
0.74
10
Authors
2
Name
Order
Citations
PageRank
Raja Jothi126413.98
Balaji Raghavachari2100177.77