Improved Approximation for Single-Sink Buy-at-Bulk Export

@incollection{citeulike:4506007, abstract = {In the single-sink buy-at-bulk network design problem we are given a subset of source nodes in a weighted undirected graph: each source node wishes to send a given amount of flow to a sink node. Moreover, a set of cable types is given, each characterized by a cost per unit length and by a capacity: the ratio cost/capacity decreases from small to large cables by economies of scale. The problem is to install cables on edges at minimum cost, such that the flow from each source to the sink can be routed simultaneously. The approximation ratio of this NP-hard problem was gradually reduced from O(log2 n) to 65.49 by a long series of papers. In this paper, we design a better 24.92 approximation algorithm for this problem.}, author = {Grandoni, Fabrizio and Italiano, Giuseppe}, citeulike-article-id = {4506007}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11940128_13}, citeulike-linkout-1 = {http://www.springerlink.com/content/3j8332076643n678}, doi = {10.1007/11940128_13}, journal = {Algorithms and Computation}, keywords = {buy-at-bulk, network\_design}, pages = {111--120}, posted-at = {2009-05-12 21:43:58}, priority = {2}, title = {Improved Approximation for Single-Sink Buy-at-Bulk}, url = {http://dx.doi.org/10.1007/11940128_13}, year = {2006} }

TY - CHAP ID - citeulike:4506007 L3 - citeulike-article-id:4506007 N2 - In the single-sink buy-at-bulk network design problem we are given a subset of source nodes in a weighted undirected graph: each source node wishes to send a given amount of flow to a sink node. Moreover, a set of cable types is given, each characterized by a cost per unit length and by a capacity: the ratio cost/capacity decreases from small to large cables by economies of scale. The problem is to install cables on edges at minimum cost, such that the flow from each source to the sink can be routed simultaneously. The approximation ratio of this NP-hard problem was gradually reduced from O(log2 n) to 65.49 by a long series of papers. In this paper, we design a better 24.92 approximation algorithm for this problem. JF - Algorithms and Computation EP - 120 TI - Improved Approximation for Single-Sink Buy-at-Bulk SP - 111 KW - buy-at-bulk KW - network_design AU - Grandoni, Fabrizio AU - Italiano, Giuseppe PY - 2006/// UR - http://dx.doi.org/10.1007/11940128_13 ER -