1、Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems,MohammadTaghi Hajiaghayi Carnegie Mellon UniversityJoint work withChandra Chekuri (UIUC) Guy Kortsarz (Rutgers, Camden) Mohammad R. Salavatipour (University of Alberta),2,Motivation,Suppose we are given a network and some n
2、odes have to be connected by cables,10,12,8,21,27,11,5,9,14,7,21,3,16,Each cable has a cost (installation or cost of usage)Question: Install cables satisfying demands at minimum cost,This is the well-studied Steiner forest problem and isNP-hard,3,Motivation (contd),Consider buying bandwidth to meet
3、demands between pairs of nodes. The cost of buying bandwidth satisfy economies of scale The capacity on a link can be purchased at discrete units:Costs will be: Where,4,So if you buy at bulk you save More generally, we have a non-decreasing monotone concave (or even sub-additive) function where f (b
4、) is the minimum cost of cables with bandwidth b.,Motivation (contd),bandwidth,cost,Question: Given a set of bandwidth demands between nodes, install sufficient capacities at minimum total cost,5,Motivation (contd),The previous problem is equivalent to the following problem: There are a set of pairs
5、 to be connected For each possible cable connection e we can:Buy it at b(e): and have unlimited useRent it at r(e): and pay for each unit of flow A feasible solution: buy and/or rent some edges to connect every si to ti. Goal: minimize the total cost,6,Motivation (contd),10,14,3,If this edge is boug
6、ht its contribution to total cost is 14.,If this edge is rented, its contribution to total cost is 2x3=6,Total cost is:where f(e) is the number of paths going over e.,7,These problems are also known as cost-distance problems:cost functionlength function Also a set of pairs of nodes each with a deman
7、d for every i Feasible solution: a set s.t. all pairs are connected in,Cost-Distance,8,Cost-Distance (contd),The cost of the solution is:where is the shortest path in The cost is the start-up cost andis the per-use cost (length).Goal: minimize total cost.,9,Multicommodity Buy At Bulk,Note that the s
8、olution may have cycles,The problem is called Multi-Commodity Buy-at-Bulk (MC-BB),5,11,8,21,12,10,Special Cases,If all si (sources) are equal we have the single-source case (SS-BB),If the cost and length functions on the edgesare all the same, i.e. each edge e has cost c + l f(e) for constantsc,l :
9、Uniform-case,5,11,8,21,12,Single-source,11,Previous Work,Formally introduced by F. S. Salman, J. Cheriyan, R. Ravi and S. Subramanian, 1997O(log n) approximation for the uniform case, i.e. each edge e has cost c+lf(e) for some fixed constants c, l (B. Awerbuch and Y. Azar, 1997; Y. Bartal, 1998)O(lo
10、g n) randomized approximation for the single-sink case: A. Meyerson, K. Munagala and S. Plotkin, 2000 O(log n) deterministic approximation for the single-sink case: C. Chekuri, S. Khanna and S. Naor, 2001,12,Hardness Results for Buy-at-Bulk Problems,Hardness of (log log n) for the single- sink case
11、J. Chuzhoy, A. Gupta, J. Naor and A. Sinha, 2005 (log1/2- n) in general M. Andrews 2004, unless NP ZPTIME(npolylog(n),13,Algorithms for Special Cases,Steiner ForestA. Agrawal, P. Klein and R. Ravi, 1991 M. X. Goemans and D. P. Williamson, 1995 Single sourceS. Guha, A. Meyerson and K. Munagala , 2001
12、 K. Talwar, 2002 A. Gupta, A. Kumar and T. Roughgarden, 2002 A. Goel and D. Estrin, 2003,14,Multicommodity Buy at Bulk,Multicommodity Uniform Case: Y. Azar and B. Awerbuch, 1997Y. Bartal,1998 A. Gupta, A. Kumar, M. Pal and T. Roughgarden, 2003 The only known approximation for the general case M. Cha
13、rikar, A. Karagiozova, 2005. The ratio is:exp( O( log D log log D )1/2 ),15,Our Main Result,Theorem: If h is the number of pairs of si,ti then there is a polytime algorithm with approximation ratio O(log4 h). For simplicity we focus on the unit-demand case (i.e. di=1 for all is) and we present O(log
14、5n loglog n).,16,Overview of the Algorithm,The algorithm iteratively finds a partial solution connecting some of the residual pairs The new pairs are then removed from the set; repeat until all pairs are connected (routed) Density of a partial solution = cost of the partial solution # of new pairs r
15、outed The algorithm tries to find low density partial solution at each iteration,17,Overview of the Algorithm (contd),The density of each partial solution is at most(log4 n) (OPT / h) where OPT is the cost of optimum solution and h is the number of unrouted pairs A simple analysis (like for set cove
16、r) shows:Total Cost (log4 n) OPT (1/n2 + 1/(n2 - 1) + 1) (log5 n) OPT,18,Structure of the Optimum,How to compute a low-density partial solution? Prove the existence of low-density one with a very specific structure: junction-tree Junction-tree: given a set P of pairs, tree T rooted at r is a junctio
17、n tree if It contains all pairs of PFor every pair si,ti P the path connecting them in T goes through r,r,19,Structure of the Optimum (contd),So the pairs in a junction tree connect via the root We show there is always a partial solution with low density that is a junction tree Observation: If we kn
18、ow the pairs participating in a junction-tree it reduces to the single-source BB problem,r,Then we could use the O(log n) approximation of MMP00,20,Summary of the Algorithm,So there are two main ingredients in the proof Theorem 2: There is always a partial solution that is a junction tree with densi
19、ty (log2 n) (OPT / h) Theorem 3: There is an O (log2 n) approximation for the problem of finding lowest density junction tree (this is low density SS-BB). Corollary: We can find a partial solution with density (log4 n) (OPT / h) This implies an approximation (log5 n) for MC-BB.,21,More Details of th
20、e Proof of Theorem 2:,We want to show there is a partial solution that is a junction tree with density (log2 n) (OPT / h) Consider an optimum solution OPT. Let E* be the edge set of OPT, OPTc be its cost and OPTl be its length. By the result of Elkin, Emek, Spielman and Tang 2005 on probabilistic di
21、stribution on spanning trees and by loosing a factor (log2 n) on length, we can assume that E* is a forest T (WLOG we assume T is connected).,22,More Details of the Proof of Theorem 2:,From T we obtain a collection of rooted subtrees T1,Ta such that any edge e of T is in at most O(log h) of the subt
22、rees For every pair there is exactly one index i such that both vertices are in Ti; further the root of Ti is their least common ancestor The total cost of the junction trees is at most (log2 h) OPT (O (log h) OPTc + (log2 h) OPTl) Thus at least one of junction trees of T1,Ta has the desired density
23、 of (log2 h) (OPT / h),23,More Details of the Proof of Theorem 2:,Given T, we pick a centeroid r1 (i.e., largest remaining component has at most 2/3 |V(T)| vertices). Add tree T rooted at r1 to the collection Remove r1 from T and apply the procedure recursively to each of the resulting component Eac
24、h pair is on exactly one subtree in the collection The depth of the recursion is in O (log h),24,Some Details of the Proof of Theorem 3:,Theorem 3: There is an approximation for finding lowest density junction tree. This is very similar to SS-BB except that we have to find a lowest density solution.
25、 Here we have to connect a subset of the pairs to the root r with lowest density (= cost of solution / # of pairs in sol).Let denote the set of paths from r to i. We formulate the problem as an IP and then consider the LP relaxation of the problem,25,Some Details of the Proof of Theorem 3:,We solve
26、the LP by setting ys=yt for each pair (s,t), and then find a subset of nodes to solve the SS-BB We find a class of y among O (log n) classes of almost equal yi with maximum sum (loose a factor O (log n) We use the O (log n) approx of MMP,CKN for SS-BB (indeed it is the upper bound on integrality gap
27、 of the LP),26,Some Remarks:,For the polynomially bounded demand case we can find low density junction-trees using a more refined region growing technique and also using a greedy algorithm (within O (log4 n)Hajiaghayi, Kortsarz and Salavatipour, ECCC 2006 The greedy algorithm is based on an algorith
28、m for the k-shallow-light tree problem Hajiaghayi, Kortsarz and Salavatipour, APPROX 2006 There is a conjectured upper bound of O (log n) for distortion in embedding a graph metric into a probability distribution over its spanning tree (Alon, Karp, Peleg and West, 1991) If true, that would improve o
29、ur approximation factor for arbitrary demands to O (log4 n),27,Some Remarks (contd):,Indeed, as suggested by Racke, our current approach can be applied via Bartals trees (and interestingly not FRT) to obtain an O(log h) factor instead of (log2 h) factorFor a constant fraction of the pairs, we use st
30、rong diameter property which is true in Bartals construction It is more technical, but we can obtain factor O (log4 h) for general demands (solving an open problem),28,Recent Extensions,The result O(log4n) can be extended to the vertex-weighted case but requires some new ideas and some extra work CH
31、KS07. Especially we obtain the tight result O(log n) for the single-sink vertex-weighted case via LP rounding Also it needs some subtle change of vertex weights to edge weights in the junction tree lemma Also our results can be extended to the stochastic versions with non-uniform inflation (by loosi
32、ng an extra factor O(log n) Gupta, Hajiaghayi, Kumar06. Some technique has been used in the Dial-a-Ride problemGupta, Hajiaghayi, Ravi, Nagarajan06.,29,Open Problems,There are still quite large gaps between upper bounds (approx alg) and lower bounds (hardness)For MC-BB: vsFor SS-BB: vs It would be nice to upper bound the integrality gap for MC-BB. Emphasize on the conjecture of Alon, Karp, Peleg and West, 1991,30,Thanks for your attention,
