Algorithmica (2002) 34: 197–215 DOI: 10.1007/s00453-002-0968-3
Algorithmica ©
2002 Springer-Verlag New York Inc.
Approximation Algorithms for Access Network Design Matthew Andrews1 and Lisa Zhang1 Abstract. We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. Trunks are available in K types reflecting economies of scale. A trunk type with a high initial overhead cost has a low cost per unit bandwidth and a trunk type with a low overhead cost has a high cost per unit bandwidth. We formulate the problem as an integer program. We first use a primal–dual approach to obtain a solution whose cost is within O(K 2 ) of optimal. Typically the value of K is small. This is the first combinatorial algorithm with an approximation ratio that is polynomial in K and is independent of the network size and the total traffic to be carried. We also explore linear program rounding techniques and prove a better approximation ratio of O(K ). Both bounds are obtained under weak assumptions on the trunk costs. Our primal–dual algorithm is motivated by the work of Jain and Vazirani on facility location [7]. Our rounding algorithm is motivated by the facility location algorithm of Shmoys et al. [12]. Key Words. Access network design, Economies of scale, Primal–dual algorithm, LP-rounding, Approximation algorithms.
1. Introduction. Many modern telecommunications networks consist of two parts, a core network and an access network. The core provides much of the switching functionality and contains relatively few nodes. The access network is used to carry traffic from the numerous endnodes into the core. One way to design an access network would be to provision capacity on a direct link from each endnode into the core. This is a sensible solution for a scenario in which the cost of a connection is linear with respect to its bandwidth. However, the cost of bandwidth typically exhibits economies of scale. That is, if we purchase bandwidth in larger pieces, then the cost per unit bandwidth is less. Hence it typically makes sense to aggregate traffic at different points in the access network before it reaches the core. We study the problem of designing an access network of minimum cost, for a given set of trunk types and an unlimited supply of trunks of each type. Each trunk type is associated with a capacity and a cost. Throughout the paper we assume that it is worthwhile to use a trunk only if a constant fraction of its capacity can be be occupied; otherwise a trunk with a smaller capacity would be less expensive. This assumption on the trunk costs is natural since it is unlikely to be economical to buy a trunk with large capacity but only occupy a small part of the capacity. We formulate the problem of access network design in terms of a linear program. In this paper we present a primal–dual scheme that leads to a solution that is within a factor O(K 2 ) of the optimal, where K is the number of trunk types. Typically K is a 1 Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974, USA. {andrews, ylz}@research.belllabs.com.
Received May 4, 2000; revised August 14, 2001. Communicated by Ming-Yang Kao. Online publication July 10, 2002.
198
M. Andrews and L. Zhang
constant, much smaller than the size of the network. In this scheme we do not solve the linear program directly. Instead, we first find a dual solution combinatorially and then construct a primal solution from the dual. Our scheme is motivated by the elegant primal–dual scheme of Jain and Vazirani [7] for facility location. However, our linear program is somewhat more involved than that for facility location and so a number of new ideas are necessary for the primal–dual analysis to carry through. One reason we feel our result is of interest is that it shows that the Jain–Vazirani ideas may be extended to more complex problems. In addition to the primal–dual approach, we pursue the technique of rounding the optimal fractional solution obtained by solving the linear program directly. We present a rounding scheme with an O(K ) approximation. The Model. We now give a formal definition of the problem. Consider a metric space with n nodes among which some are endnodes and some are core nodes. Each endnode i has an integral demand di that needs to be routed from i to a core node. Each link e has a length e and the lengths of all links satisfy the triangle inequality. We are given K types of trunks to carry demands along each link. We use (e, k) to refer to a type-k trunk on link e. Traditionally, each trunk type k is associated with capacity ck and a cost pk per unit length. Trunks with higher capacity have a lower cost per unit demand. Thus, routing d units of demand for units of distance requires d/ck type-k trunks at a total cost of (1)
d/ck · pk · .
The above cost structure can be difficult to work with especially in a linear program formulation. Hence, in this paper we use a different but comparable structure. For each trunk type k we associate an overhead cost σk per unit length and a service charge µk per unit length per unit demand. For a link e, the overhead cost σk e represents the initial cost that we must pay for placing a type-k trunk on link e. The service charge µk e represents the extra cost that we must pay for routing each unit of demand on (e, k). Hence, the total cost of routing d units of demand on (e, k) is (2)
(σk + µk · d) · e .
Note that the amount of demand that can be routed along one particular trunk is unlimited in our cost structure. This removes the capacity constraints and makes the design problem easier. If the overhead σk is set to pk and the service charge µk is set to pk /ck , the quantity (2) is within a factor of 2 of (1). Hence, our “overhead/service-charge” structure is comparable with the traditional “capacity/cost” structure. With these definitions in place we define the problem of access network design. We wish to buy trunks on the links so that each demand can be routed from its source endnode to a core node. Our objective is to minimize the overhead cost incurred in buying these trunks plus the service charge incurred in routing each demand to the core. Throughout this paper we assume that the economies of scale between consecutive trunk types are not too extreme. In practice, it is unlikely to be economical to buy a trunk with large capacity and then only use a small part of that capacity. In the “overhead/service-charge” structure, this translates into the following notion. A type-k trunk is α-utilized if the service charge paid is at least α times the overhead cost, i.e. if
Approximation Algorithms for Access Network Design
199
d · µk ≥ α · σk where d is the total demand carried on (e, k). We assume that the trunk costs are such that a type-k trunk is cheaper than a type-(k − 1) trunk only if the type-k trunk is α-utilized for some constant α.2 We also assume that each type-1 trunk carrying nonzero demand is α-utilized. For simplicity let α be 12 . In summary, we assume that the cost function satisfies the following properties: 1.1. σ1 < σ2 < · · · < σ K and µ1 > µ2 > · · · > µ K . 1.2. For 2 ≤ k ≤ K , if d · µk < 12 · σk , then d · µk−1 + σk−1 < d · µk + σk . For k = 1, µ1 > 12 · σ1 . 1.3. For 2 ≤ k ≤ K , κ
2
200
M. Andrews and L. Zhang
Summary. In Section 2 we describe the structure of a near-optimal solution. In Section 3 we present a linear programming formulation of the problem. In the remainder of the paper we describe our approximation algorithms: • In Section 4 we present a primal–dual scheme and prove an approximation ratio of O(K 2 ). This is the first combinatorial algorithm with an approximation guarantee that is polynomial in K and is independent of the size of the network. • In Section 5 we present a rounding scheme and prove an approximation ratio of O(K ).
2. The Structure of a Near-Optimal Solution. In this section we explore the structural properties of the solution. We show that there is a near-optimal solution in which every trunk is 12 -utilized and each demand is routed on consecutive ascending trunk types. Therefore, in Sections 4 and 5 we can include these two structural properties in our linear programming formulation and take advantage of them in our analysis. LEMMA 1. There exists an optimal solution, TREE, in which the trunks used form a set of trees rooted at the core nodes. PROOF. We begin with any optimal solution OPT. Let T be the set of the trunks bought by OPT. We now route each demand using the trunks in T only. In particular, each demand is routed through a path that incurs the least service charge. A shortest path algorithm can choose these paths so that the trunks used form a set of trees rooted at the core. These paths define the solution TREE. We note that TREE has the optimal cost. TREE incurs the least service charge among all solutions that use the trunks in T only. In particular, TREE incurs no more service charge than OPT does. Furthermore, TREE uses trunks in T only and therefore incurs no more overhead charge than OPT. Due to the optimality of TREE, each trunk in TREE is 12 -utilized. Furthermore, each demand is routed through a sequence of trunks of nondecreasing types. This is true since demands are only merged and never split. We transform TREE into a near-optimal solution with more restrictions without increasing the total cost by much. LEMMA 2. There exists a near-optimal solution that satisfies Properties 2.1 and 2.2 and whose cost is O(1) times the cost of TREE. 2.1. Each demand is routed through trunks of consecutive types, i.e. types 1, 2, . . . , κ. 2.2. Each trunk that is used is 12 -utilized. PROOF. We assume inductively that the subtree rooted at node u satisfies Properties 2.1 and 2.2. For the base case in which u is a leaf node of TREE, the properties hold trivially for a 1-node tree.
Approximation Algorithms for Access Network Design
201
Let (uv, kuv ) be the outgoing trunk of u. (Note that there is only one outgoing link.) We now try to enforce Properties 2.1 and 2.2 for the subtree rooted at v. Consider all the incoming trunks to u. Initially, all incoming trunks are regarded as untreated. We first choose from the untreated set the trunks with the smallest type and mark them treated. Suppose this smallest type is k and a total of d units of demand enter u via type-k trunks. We find the largest type κ ≤ kuv such that a type-κ trunk would be 12 -utilized for a demand of d units. • Case 1. If κ is smaller than any trunk-type of the untreated set, then we put down trunks (uv, κ), and 0-length trunks of types k+1, . . . , κ −1 at u. The demand of d units now enters u via type-k trunks, travels through these 0-length trunks of consecutively increasing types and leaves u via (uv, κ). • Case 2. Otherwise, κ is greater than or equal to some trunk-type of the untreated set. We put down 0-length trunks of types k + 1, . . . , κ at u. We regard the demand of d units as traveling through these 0-length trunks and then reentering u after passing through the type-κ trunk. This type-κ trunk is currently untreated. We repeat this process until all incoming trunks are treated. Figure 1 (Steps 1–3) illustrates the above process in a simple example. The untreated trunks are shown with solid lines and the treated trunks are shown with dotted lines. The above process can increase both overhead charge and service charge. All the new trunks we put down are either of 0 length; or they are along uv and are distinct types strictly lower than kuv . Hence, the total overhead and service charge due to these new trunks is at most κ
(µκ dκuv + σκ )uv ,
v
4
6
3
u 5
3
2
5
Initial
Step 1
2
Final
Step 2
5
3
3
Step 4
Step 3
4 3
2
3
5 5
Fig. 1. Initial configuration: five trunks of types 2, 3 and 5 enter (uv, 6). Step 1: two type-2 trunks merge into a 0-length type-3 trunk. Step 2: two type-3 trunks merge and enter new trunk (uv, 4). Step 3: two type-5 trunks merge and enter new trunk (uv, 5). Step 4: type-5 trunks shortcut. Final configuration is obtained.
202
M. Andrews and L. Zhang
where dκuv is the demand carried on the new trunk (uv, κ). Recall that trunk (uv, κ + 1) would be less than 12 -utilized for the demand of dκuv units. Hence, by Property 1.2, κ
(µκ dκuv + σκ )uv ≤ ≤
κ
κ
=
κ≤kuv
(µκ+1 dκuv + σκ+1 )uv ( 12 · σκ+1 + σκ+1 )uv 3 2
· σκ uv .
The total overhead and service charge due to these new trunks along uv is O(σkuv uv ) if κ≤kuv σκ = O(σkuv ). The final part of the construction is to shortcut the trunks for all types κ, i.e. we reroute any demand that used to follow (v u, κ) and (uv, κ) so that it now follows (v v, κ). See Figure 1, Step 4. Shortcutting does not increase the service charge, since the distance function satisfies the triangle inequality. Since all trunks are 12 -utilized, the overhead charge is at most twice the service charge on any trunk. Hence, the increase in the overhead charge due to shortcutting trunk (v v, κ) is at most twice the service charge on trunk (uv, κ). Observe that the total service charge on all the trunks along uv is at most O(σkuv uv ) + µkuv duv uv , where duv is the total demand that was originally routed through (uv, kuv ). The first term upperbounds the service charge on the new trunks along uv and the second term is the original service charge along (uv, kuv ). This completes the transformation of the subtree rooted at u while preserving Properties 2.1 and 2.2. The increase in total cost is bounded by O(σkuv uv + µkuv duv uv ). Hence, the total cost of the intermediate solution is within a constant factor of that of TREE. If we do not have the condition κ≤kuv σκ = O(σkuv ), then the increase in total cost due to the transformation of (uv, kuv ) is bounded by kuv O(σkuv uv + µkuv duv uv ). Hence, in this case the total cost of the intermediate solution is O(K ) times that of TREE.
3. A Linear Program Formulation. The optimal solution restricted by Properties 2.1 and 2.2 can be expressed by an integer program formulation, IP-ACCESS. We begin with some notation. We use (uv, k) to represent a type-k trunk along link uv. We also have 0-length self-loops, (uu, k), for every node u and every trunk type k. Such self-loops are necessary to enforce Property 2.2 of consecutive trunk types. We use letters such as u, v and w to represent a generic node which can be an endnode or a core node; we use i and j to represent endnodes only, and we use c to represent a core node in the core C. The variables xke ∈ {0, 1} represent whether or not trunk (e, k) is bought. The variables e yk,i ∈ {0, 1} represent whether or not the demand from endnode i is routed through trunk (e, k). Recall that e is the length of link e, di is the demand from endnode i, and σk and µk are the overhead and service charges of a type-k trunk, respectively. The objective function is to minimize the total cost, i.e. the sum of the overhead cost for all trunks
Approximation Algorithms for Access Network Design
203
bought and the service charge for all demand. Constraints (3), (4) and (5) enforce flow conservation and Property 2.1 of consecutive trunk types. Constraint (6) guarantees that if some demand is routed through a trunk, then the overhead cost of the trunk is paid for. Constraint (7) enforces Property 2.2 of 12 -utilization. (IP-ACCESS) min
K e
e σk xke
+
K e
k=1
e µ k
e di yk,i
i
k=1
subject to (3) (4)
v
vu yk,i =
v
uv yk+1,i ,
∀i, u ∈ / C,
iu y1,i = 1,
∀i,
uc yk,i = 1,
∀i,
1 ≤ k < K,
u
(5) (6) (7) (8) (9)
K k=1 c∈C u
e yk,i ≤ xke ,
σk xke ≤ 2µk
xke ∈ {0, 1}, e ∈ {0, 1}, yk,i
∀e, k, i,
e , di yk,i
∀e, k,
i
∀e, k, ∀e, k, i.
By relaxing the integrality constraints (8) and (9) to 0 ≤ xke ≤ 1, e ≤ 1, 0 ≤ yk,i
∀e, k, ∀e, k, i,
we obtain a linear program LP-ACCESS. The linear program LP-ACCESS can be solved optimally in polynomial time. However, solving LP-ACCESS can still be somewhat slow for large networks. In Section 4 we exploit the structure of the dual program and find a dual solution combinatorially and quickly. The dual solution offers a lower bound on the optimal primal solution which can be fractional. The optimal fractional solution in turn lower bounds OPT, the optimal integral solution. From the dual solution, we construct an integral primal solution whose total cost is within O(K 2 ) of the dual solution we have found. In Section 5 we obtain a better approximation of O(K ). For this scheme, we solve the linear program directly and round the fractional solution so that the resulting integral solution is within a factor O(K ) of the optimal fractional solution.
4. The Primal–Dual Approach 4.1. A Dual Solution.
The dual of LP-ACCESS is as follows:
204
M. Andrews and L. Zhang
(DUAL-ACCESS) max
i di ρ0,i
i
subject to (10)
u e v + ρk−1,i ≤ e µk − 2µk γke + βk,i /di , −ρk,i
∀i, v ∈ / C, e = uv, {1 < k < K , u ∈ / C} or {k = 1, u = i},
(11)
u e ρk−1,i ≤ e µk − 2µk γke + βk,i /di ,
∀i, c ∈ C, e = uc, {1 < k < K , u ∈ / C} or {k = 1, u = i},
(12)
−σk γke +
i
e βk,i /di ≤ e σk , e βk,i ≥ 0, e γk ≥ 0,
∀k, e, ∀k, e, i, ∀k, e.
i For simplicity we use αi to represent ρ0,i . Hence the objective function is i di αi . We construct a dual solution by gradually increasing the α-variables, β-variables and γ -variables. We then choose the ρ-variables so as to maintain dual feasibility. We use a notion of time to measure the rate at which variables change. Our goal is to make the dual objective as large as possible while maintaining all dual constraints at all times. The strategy is to uniformly increase the α’s as much as possible. When constraints (10) and (11) become tight, we increase the β’s at a “faster” rate and the γ ’s at a “slower” rate to make more room for the α’s to increase. However, increasing the β’s and γ ’s in such a manner eventually makes constraints (12) tight. Consequently, the β’s and γ ’s have to stop increasing. Although the high level idea is simple, a precise description of the procedure is somewhat complicated since the variables interact with one another. Whether or not each individual variable should change is decided by the values of many other variables at that moment. e We define the gain of a demand i on a trunk (e, k) to be e µk − 2µk γke + βk,i /di , i.e. u the right-hand side of constraints (10) and (11). For k > 0, we always define ρk,i to be the least total gain along any path from u to the core using consecutive trunk types k + 1 and higher. The dual objective is to maximize the weighted sum of the least total gain path from each endnode to the core using consecutive ascending trunk types. Finding a Dual Solution. We first define the rate at which variables increase. When e increases, it αi increases, it increases at rate 1 (i.e. the same rate as time). When βk,i e increases at rate 3di for all (e, k) and i. When γk increases, it increases at rate 1/µk for all (e, k). The key is to determine when the β-variables and the γ -variables should be u increased. As stated above, for k > 0 the variable ρk,i is always equal to the least total gain along any path from u to the core using consecutive trunk types k + 1 and higher. At time zero, the α, β and γ variables all equal zero.
Approximation Algorithms for Access Network Design
205
We say that a path p is a bottleneck path for i at time t if (e,k)∈ p e µk ≤ (2K + 1)t. When path p becomes a bottleneck path for i we make extra room for αi to increase by exploiting unexhausted trunks on path p. We say that a trunk (e, k) is exhausted if constraint (12) that involves (e, k) is tight.3 As soon as path p becomes a bottleneck path e we start to increase βk,i (at rate 3di ) for all unexhausted trunks (e, k) on path p. We say that i contributes to these unexhausted trunks. If γke is not already increasing, then we e start to increase then they do not start to increase γke (at rate 1/µk ). Once γke and βk,i stop increasing until trunk (e, k) is exhausted. At some point there will be a bottleneck path for i on which every trunk is exhausted. As soon as αi equals the total gain on such a path we say αi is complete and call this bottleneck path the critical path for i. (If multiple such paths exist, an arbitrary one is chosen.) When αi is complete, we stop increasing it. When αi is complete for all i, we have found our dual solution. We use α¯ i to denote the value of αi at its completion. Correctness. We need to make sure that the current value of our variables define a feasible dual solution. The solution can be infeasible only if the total gain along some path from endnode i to the core is smaller than αi for some i. Consider any path p from
p becomes a bottleneck path for demand i. i to the core and let t be the time at which Therefore (e,k)∈ p e µk = (2K + 1)t . At all times before time t , we have αi ≤ t . In addition γke µk ≤ t for all (e, k). Therefore, e e µ k − 2γke µk + βk,i . αi ≤ (2K + 1)t − 2K t ≤ (e,k)∈ p
(e,k)∈ p
(e,k)∈ p
The right-hand side is equal to the total gain on path p. Hence path p does not violate any constraints before time t . At all times after time t the gain for demand i on a trunk (e, k) ∈ p never decreases. Moreover, if (e, k) is unexhausted, then the gain actually increases at rate 1. This is e because βk,i /di is increasing at rate 3 and 2γke µk is increasing at rate 2. Hence if there are any unexhausted trunks on path p, then the total gain on p increases faster than αi , since αi increases at rate at most 1. When all the trunks on p are exhausted then αi becomes complete if it ever equals the total gain on p. When αi is complete, it stops increasing. This argument shows that αi is never larger than the total gain on path p. Running Time. We now bound the running time for finding our dual solution. We first work out when trunk (e, k) becomes part of a bottleneck path for demand i. This requires finding a path from the endnode of i to a core node that passes through (e, k) and has the smallest service charge for each unit of demand routed. An all-pairs shortest path algorithm is sufficient for this purpose. Once we know when a trunk (e, k) becomes part of a bottleneck path for each i, we e then work out when the βk,i and γke start increasing and when trunk (e, k) is exhausted. This definition is only precise when e > 0. When e = 0, constraint (12) is tight initially since β and γ are equal to 0. In some cases these β and γ can be increased without violating (12), and it is necessary to do so in order to increase α. To avoid adding special cases to the algorithm we can use a small positive value as the length of a 0-length trunk. The primal solution will be increased by a small amount only and our overall approximation will not be changed asymptotically. We do not get into details here. 3
206
M. Andrews and L. Zhang
Whenever a trunk becomes exhausted it affects the time at which αi becomes complete. Hence we have to recalculate the least gain path from each endnode i to a core node using exhausted trunks only. This latter process dominates the running time for finding the dual. There are n 2 K trunks in total, each of which can become exhausted. Therefore we can find the dual solution in O(n 2 K · TAPSP ) time, where TAPSP is the time taken to solve an all-pairs shortest path problem. Time Stamps. To construct a primal solution later, we need to define a time stamp τ (e, k) for every trunk (e, k) along the critical paths. Suppose (e, k) is exhausted at time t. If (e, k) is incident to a core node, then τ (e, k) = t. Otherwise, (e, k) is connected to some (e , k + 1) on a critical path p. Inductively, we define τ (e, k) = max{t, τ (e , k + 1)}. Our definition of time stamps ensures that every type-k trunk along a critical path is connected to some type-(k + 1) trunk whose time stamp is no larger. The following two lemmas are important for our analysis. LEMMA 3. Let trunk (e, k) be exhausted, and let I be the set of demands that contribute to (e, k). Then the total demands from I make (e, k) 13 -utilized, i.e. i∈I di µk ≥ 13 · σk . e PROOF. Let τ be the time stamp on (e, k). Let f = −σk γke + i βk,i /di − e σk . Since f ≤ 0 at time 0 and f = 0 at time τ , there exists a time t ∈ (0, τ ) at which d f /dt ≥ 0. At time t , 0≤
e dγ e dβk,i df −σk + 3di . ≤ −σk k + = dt dt dt µk i∈I i∈I
e The second inequality holds since βk,i increases only if i contributes to (e, k). Our lemma follows.
LEMMA 4. Suppose a trunk (e, k) is on a critical path and has a time stamp τ . If demand i contributes to (e, k), then there exists a path from i to the core via (e, k) such that sending one unit of demand along this path incurs service charge O(K )τ . Furthermore, the path uses consecutive trunk types, 1, 2, etc. PROOF. If i contributes to (e, k), then some path p becomes a bottleneck from i at a time t before (e, k) is exhausted. Therefore, t is at most the time stamp τ . By definition of bottleneck paths, the service charge for sending one unit of demand along path p is (2K + 1)t = O(K )τ . The lemma follows. 4.2. An Integral Primal Solution. Our dual solution finds a critical path from every endnode to the core. However, we cannot bound the total cost if every trunk along the critical paths is bought. In the following we show how to use the critical paths to construct an integral primal solution whose cost is within O(K 2 ) of i di α¯ i . Hence, the intergal primal solution is within O(K 2 ) of the optimal. For the remainder of this section, we only consider trunks along critical paths and the image of such trunks (defined below). We therefore refer to “a trunk along a critical
Approximation Algorithms for Access Network Design
207
path” simply as “a trunk.” When there is no confusion, we also do not distinguish a trunk from its image. It takes K iterations to construct a primal solution. We begin with the highest trunk type K . During iteration K − k + 1, we first buy a subset of the type-k trunks. We inductively assume the type-k trunks are 13 -utilized and have small service charge. We show how to bound the overhead on each trunk bought with the service charge, which in turn is bounded by induction. We then reroute type-(k − 1) trunks to make sure that they are connected to the type-k trunks already bought. When (vu, k − 1) is rerouted along (vw, k − 1) (where we allow w = u), we call the latter the image of the former and the former the origin of the latter. An image also inherits the time stamp and the set of contributing demands from its origin. We show that the images are 13 -utilized and have small service charges, and these two properties serve as the inductive hypotheses for the next iteration. During the next iteration K − k + 2, the type-(k − 1) trunks that we consider for buying are the images of the original type-(k − 1) trunks on critical paths. Inductive Hypotheses. At the beginning of iteration K − k + 1, the type-k trunks, or more precisely the images of the type-k trunks along critical paths, have the following properties. Note that time stamps and contributing demands are well defined for images. 1. Let I be the set of demands that contribute to a trunk (e, k). Then the total demands from I make (e, k) 13 -utilized. 2. The service charge for sending one unit of demand along a trunk (e, k) is O(K ) · τ (e, k), where τ (·) represents the time stamp. At the beginning of iteration 1 every type-K trunk is its own image. The two inductive hypotheses hold as a result of Lemmas 3 and 4, respectively. We describe iteration K − k + 1 in the following. Buying. We order the type-k trunks in the increasing order of their time stamps. All trunks are eligible initially. We pick an eligible trunk (e, k) with the smallest time stamp and call it a leader. If i ∈ δ(e, k) contributes to an eligible trunk (e , k), then (e , k) is made ineligible. We stop when every exhausted trunk is ineligible. To determine which trunks to buy, we find a deputy for each leader as follows. For a leader (e, k), let j = argmini∈δ(e,k) α¯ i . The trunk (ed , k) along the critical path from j is defined to be the deputy of (e, k). We buy all the deputy trunks. Given the first inductive assumption, one can verify that the deputy trunks satisfy the property described in Lemma 5 (whereas the leader trunks do not necessarily do so). Such a property is essential for bounding the overhead cost as shown in Lemma 6. LEMMA 5. The time stamp on a deputy trunk (ed , k), is at most mini∈δ(e,k) α¯ i where (e, k) is the leader. LEMMA 6.
The total overhead cost for the type-k trunks bought is O(K ) · OPT.
208
M. Andrews and L. Zhang
PROOF. By Lemma 3 the demands from the set δ(e, k) make each leader trunk (e, k) 1 -utilized. These demands also make the deputy (ed , k) 13 -utilized. Furthermore, the 3 demand sets δ(e, k) form a partition of all demands. Hence, we bound the overhead charge on a deputy trunk (ed , k) by bounding the service charge on (ed , k) using the demands from δ(e, k). The total service charge on deputy trunks is di µk ed ≤ di O(K )τ (ed , k) ≤ O(K ) di α¯ i = O(K ) · OPT. (ed ,k) i∈δ(e,k)
(ed ,k) i∈δ(e,k)
i
The first inequality is by induction. The second inequality follows from Lemma 5. Rerouting. Since we only bought the deputy trunks, a type-(k − 1) trunk may not be connected to any type-k trunks already bought. Hence, we need to reroute some of the type-(k − 1) trunks. Consider (vu, k − 1), and let T be the set of type-k trunks leaving u. Let (uu , k) ∈ T be the trunk with the smallest time stamp among trunks in T . If (uu , k) is bought (i.e. is a deputy), then no rerouting is needed, and (vu, k) is its own image. If (uu , k) is not bought, then either (uu , k) is a leader or (uu , k) was made ineligible by a leader. In either case the deputy of this leader was bought, and we call this deputy (ww , k). We now reroute (vu, k − 1) along (vw, k − 1). We say (vw, k − 1) is the image of (vu, k − 1) and (vu, k − 1) is the origin of (vw, k − 1). Again, an image inherits the same time stamp and the set of contributing demands from its origin. The significance of (ww , k) is that it has a “small” time stamp which allows us to bound the service charge along the image (Figure 2). LEMMA 7. The service charge for sending one unit of demand along (vw, k − 1) is O(K ) · τ (vw, k − 1), where τ (·) represents the time stamp. PROOF. If the image (vw, k − 1) is the same as (vu, k − 1), then the lemma follows from Lemma 4 since (vu, k − 1) is an original trunk along a critical path. Otherwise, the image (vw, k − 1) is different from the origin (vu, k − 1). u0
x0
w0
leader u
origin
deputy
x
w
image
v
p1
p2
i
p3
p4
j
Fig. 2. The service charge along an image is O(K ) times its time stamp.
Approximation Algorithms for Access Network Design
209
Either (uu , k) is a leader; or else let (x x , k) be the leader that made (uu , k) ineligible. We analyze the latter case, since the former is simpler. We use the term unit service charge to refer to the service charge of routing one unit of demand along a path or trunk. By the definition of leader, there exists a demand i that contributes to both (uu , k) and (x x , k). By Lemma 4, there exists a path from i to the core via the origin of (uu , k) whose unit service charge is O(K ) · τ (uu , k). Hence there is a path p1 from i to u whose unit service charge is O(K ) · τ (uu , k). Similarly, there is a path p2 from i to x whose unit service charge is O(K ) · τ (x x , k). By our construction, the trunk (ww , k) is the deputy of (x x , k). Hence, there exists a demand j that contributes to both (x x , k) and (ww , k). By a similar argument as before, there exist a path p3 from j to x whose unit service charge is O(K ) · τ (x x , k) and a path p4 from j to w whose unit service charge is O(K ) · τ (ww , k). Lemma 4 also shows that the unit service charge along (vu, k − 1) is O(K ) · τ (vu, k − 1). By the triangle inequality and the fact that p1 , p2 , p3 , p4 and (vu, k − 1) consist of trunks of type 1 through k − 1 only, the unit service charge along (vw, k − 1) is bounded by (13)
O(K )(τ (uu , k) + 2τ (x x , k) + τ (ww , k) + τ (vu, k − 1)).
We also have (14)
τ (vu, k − 1) ≥ τ (uu , k) ≥ τ (x x , k) ≥ τ (ww , k).
The first inequality is due to the inductive definition of time stamps. The second and third inequalities are due to our procedure for buying type-k trunks. Combining (13) and (14), we obtain our lemma. The proof of Lemma 7 also justifies the following, which we use to bound the total service charge after the primal solution is constructed. LEMMA 8. Trunk (vw, k − 1), the image of (vu, k − 1), connects to (ww , k) which is already bought and has a time stamp no bigger than (vw, k − 1). Lemma 7 provides the second inductive hypothesis for the next iteration. The fact that an image has the same contributing demands as its origin provides the first inductive hypothesis. Hence, our inductive step is complete. Finishing Up. Lemma 8 guarantees that at the end of the last stage each demand i has a path p = {(e1 , 1), (e2 , 2), . . . , (eκ , κ)} from its endnode to the core, where each trunk along p is bought. By Lemma 7, the total service charge for sending di units of demand along p is di · O(K )τ (ek , k). 1≤k≤κ
The time stamps satisfy τ (e1 , 1) ≥ τ (e2 , 2) ≥ · · · ≥ τ (ek , k) by Lemma 8 and α¯ i ≥ τ (e1 , 1) by the definitions of α¯ i and time stamps. Hence, the service charge incurred by the demand i is at most di · k · O(K ) · α¯ i = O(K 2 ) · di α¯ i .
210
M. Andrews and L. Zhang
Summing over all demands, we obtain LEMMA 9.
The total service charge due to our primal solution is O(K 2 ) · OPT.
As we discussed before, the dual solution can be constructed in time O(n 2 K · TAPSP ), where TAPSP is the time that it takes to solve an all-pairs shortest path problem. For the construction of the primal solution, the running time is dominated by the time taken to sort the time stamps. Hence the primal solution can be constructed in time O(n 2 K log(n 2 K )). By combining Lemmas 6 and 9 we obtain THEOREM 10. The primal–dual algorithm constructs in time O(n 2 K · TAPSP ) a solution whose cost is within a factor O(K 2 ) of the optimal.
5. LP Rounding. The linear program LP-ACCESS can be solved optimally in polynoe be the optimal fractional solution. We proceed to round x¯ke mial time. Let x¯ke and y¯k,i e and y¯k,i so that the total cost of the rounded solution is within a factor O(K ) of the optimal fractional solution. Hence, the rounded solution is within a factor O(K ) of the optimal. Path Decomposition. For each endnode i, we first decompose the flow from i into paths. The flow paths are chosen one by one on the subgraph induced by the trunks (e, k), where e > 0. Each path p from an endnode i is chosen so that it follows a sequence of trunks y¯k,i of consecutive ascending types. This is always possible due to constraints (3)–(5). The amount of flow along p is set to the maximum possible, which means at least one trunk along p will carry no flow from endnode i after p is chosen. The flow decomposition can be done in polynomial time. The result of the path decomposition allows us to define two useful quantities that carry the notion of “average” service charge. Let Pi be the set of flow paths from i. Let p ∈ Pi carry an f ( p) fraction of the demand from i and let the service charge for sending one unit of demand along p be s( p). We define (15)
gi =
f ( p)s( p)
p∈Pi
to be the total service charge for sending one unit of demand from endnode i. We also define (16)
t ( p) = max{2gi , s( p)},
for
p ∈ Pi .
A path p ∈ Pi is short if s( p) ≤ 2gi ; p is long otherwise. The total service charge is i di gi , most of which is incurred on short paths. We would like to work with short paths only. However, in order to make use of 12 -utilization in bounding the overhead costs we cannot simply load the flow from the long paths onto the short paths (as in [12],
Approximation Algorithms for Access Network Design
211
[8], and [13]). It is immediate that LEMMA 11. For every endnode i, 1. f ( p) > 12 , i.e. the short paths together carry more than half of the demand; short p∈Pi 2. p∈Pi f ( p)t ( p) = (gi ). Overview and Inductive Hypotheses. Rounding x¯ke to 1 or 0 corresponds to whether or not we buy trunk (e, k). The rounding algorithm here resembles the construction of the integral primal solution in Section 4.2 although the analysis is more complex. As before, the rounding takes K iterations and it begins with the highest trunk type K . During iteration K − k + 1, we first buy a subset of the type-k trunks and then reroute type-(k − 1) trunks to make sure that they are connected to the type-k trunks already bought. As in the primal–dual approach, the trunks that carry out the rerouting are called images. The type-(k − 1) trunks that we consider buying during the next iteration are actually these images. Inductively, we assume the following at the beginning of iteration K − k + 1. (At the beginning of iteration 1, these properties hold trivially.) e 1. y¯k,i ≤ x¯ke for every trunk (e, k) and every endnode i. 2. Every type-k trunk is 12 -utilized. 3. The total service charge along all the type-k trunks is O(1) · OPT.
The route of p may be modified due to our rounding. Two flow paths may be merged to the same route, but we keep track of them separately. Whether p is long or short and the values of gi and t ( p) are determined once and for all by the flow decomposition, no matter how p is subsequently rerouted. Buying. We now present iteration K − k + 1 in full detail. We first order the endnodes in increasing order of gi . At the beginning, all endnodes are eligible. We pick an eligible endnode with the smallest gi and call i a leader. Let Pi be the set of short paths from i. If some path p ∈ Pi does not go through a type-k trunk, then p enters a core node w via a trunk of type smaller than k. We call w the candidate of i. Otherwise, every path p ∈ Pi goes through a type-k trunk, among which we buy the shortest one, (ww , k). We call w the candidate of i. If a short path from an eligible endnode i meets a short path from i at a node u following two type-(k − 1) trunks (say (v1 u, k − 1) and (v2 u, k − 1)), then i becomes a follower of i and the candidate of i also becomes the candidate of i . (Our definition of followers ensures that a follower is “close” to its leader.) Endnode i and its followers now become ineligible. We repeat the process of choosing an eligible endnode with the smallest gi until no endnode is eligible. At this moment, each endnode has a candidate. We now round x¯ke to 1 if (e, k) is bought and round x¯ke to 0 otherwise. LEMMA 12.
The total overhead cost for the type-k trunks bought is O(1) · OPT.
PROOF. During iteration K − k + 1, let E i be the set of trunks (e, k) that are on the short paths of leader i at the beginning of iteration K − k + 1. If the candidate for i is a core
212
M. Andrews and L. Zhang
node, then no type-k trunk is bought due to i. Otherwise, the shortest trunk (ei , k) ∈ E i is bought and all other trunks in E i are not bought. The total fractional overhead cost due to the trunks in E i is e∈E
x¯ke e σk ≥ ei σk
e∈E
x¯ke ≥ ei σk
e y¯k,i ≥
1 2
· ei σk ,
e∈E
which equals half of the overhead cost for buying the whole of (ei , k). The first inequality holds since (ei , k) is the shortest trunk in E i . The second inequality holds due to the first inductive hypothesis. The last inequality holds due to condition 1 of Lemma 11. For two leaders i and j, their corresponding sets of trunks E i and E j are disjoint. Hence, the total overhead cost for the type-k trunks bought during iteration K − k + 1 is at most twice the fractional overhead cost for fractional type-k trunks present at the beginning of iteration K − k + 1. At the beginning of iteration K − k + 1, every type-k trunk is 12 -utilized due to the second inductive hypothesis, and the total service charge along all the type-k trunks is O(1) · OPT due to the third inductive hypothesis. Our lemma follows. COROLLARY 13. of rounding.
The total overhead cost paid is O(K ) · OPT at the end of K iterations
Rerouting. Any positive flow on trunks (e, k) where x¯ke = 0 needs rerouting. Otherwise, the first inductive hypothesis cannot be maintained for the next iteration. We go through every trunk (vu, k − 1) that carries positive flow. Let P be the flow paths that currently go through (vu, k − 1). Let q = argmin p∈P t ( p) be the flow path that minimizes t (·), where t (·) is defined in (16). Suppose q originates from endnode j and let w be the candidate for j. We reroute all the paths in P from v to w along a trunk (vw, k − 1). Once at w each flow path can follow a path to the core along trunks that are bought already. Furthermore, each flow path follows the path that incurs the least service charge from w to the core. vu vu e vw We first set x¯k−1 to x¯k−1 and then set x¯k−1 to 0. We also set the values of y¯κ,i , for κ ≥ k − 1, to reflect the change in the flow paths. Since all the flow paths that used to be along (vu, k − 1) now follow (vw, k − 1), the second inductive hypothesis of 1 -utilization is maintained. Furthermore, since each flow path follows trunks that are 2 already bought for type k or higher and each flow path is currently unchanged for type k − 2 or lower, the first inductive hypothesis is maintained. It remains to verify the third inductive hypothesis. Let p be a path as a result of flow decomposition. We use sk ( p) to denote the service charge for sending one unit of demand along p at the beginning of iteration K − k + 1. Recall also the definitions of gi and t ( p) from (15) and (16). We emphasize that gi and t ( p) are defined in terms of s K ( p), i.e. the service charge before rounding starts.
Approximation Algorithms for Access Network Design
213
LEMMA 14. 1. The service charge along all the type-(k − 1) trunks is O( i di gi ) at the end of iteration K − k + 1. 2. sk ( p) < 5(K − k + 1)t ( p) for all p and for all 1 ≤ k ≤ K . PROOF. Let P be the set of flow paths that go through trunk (vu, k − 1) at the beginning of iteration K − k + 1. Let q = argmin p∈P t ( p) be the flow path that minimizes t ( p). Suppose q originates from endnode j and let w be the candidate for j. We show that the service charge for sending one unit of demand on (vw, k − 1) is at most 4t (q). If the endnode j is a leader, then it has a short path q1 to the core via w. Let c1 and c2 be, respectively, the service charge for sending one unit of demand from j to v along q and from j to w along q1 . We have vw µk−1 ≤ c1 + c2 ≤ s K (q) + 2g j ≤ 2t (q).
(17)
The first inequality comes from the triangle inequality, and the fact that c1 and c2 consist of service charges from trunk types 1 through k − 1 only. For the second inequality, c1 ≤ t (q) since the trunks of types 1 through k − 2 are not yet affected by the rounding procedure; c2 ≤ 2g j since q1 is short. The last inequality is due to the definition of t (q). If the endnode j is a follower of j , then a short path q2 from j meets a short path q3 from j at a node x following type-(k − 1) trunks. In addition, a short path q1 from j goes to the core via w (Figure 3). Let c1 , c2 , c3 and c4 be, respectively, the unit service charge from j to v along q, from j to x along q2 , from j to x along q3 , from j to w along q1 . We have vw µk−1 ≤ c1 + c2 + c3 + c4 ≤ t (q) + 2g j + 2g j + 2g j
(18)
≤ t (q) + 2g j + 2g j + 2g j ≤ 4t (q). The first, second and last inequalities hold by a reasoning similar to that used for the inequalities in (17). The third inequality holds since j is a leader of j and hence g j ≤ g j . u
w,
candidate for
j
u
w,
reroute
v
q
leader
q1
j
j
reroute
v
p
candidate for
p
x
q
q2
follower
q3
j
leader
q1
j0
Fig. 3. Bounding service charge on a rerouting trunk. (Left) Path q comes from a leader endnode j. (Right) Path q comes from a follower endnode j.
214
M. Andrews and L. Zhang
Since all the flow paths in P are rerouted along (vw, k − 1), the total service charge along (vw, k − 1) is at most 4t (q) f ( p)di( p) ≤ 4t ( p) f ( p)di( p) , p∈P
p∈P
where i( p) is the endnode of p. The above inequality holds since t (q) ≤ t ( p) for all p ∈ P by the definition of q. Observe that the set of flow paths that go through one type-(k − 1) trunk are disjoint from the set that goes through another type-(k − 1) trunk. Hence, the total service charge along all the type-(k − 1) rerouting trunks is at most 4t ( p) f ( p)di( p) = di 4t ( p) f ( p) = gi di , p
i
p∈Pi
i
where Pi is the set of flow paths from endnode i. The last equality above follows from condition 2 of Lemma 11. Part 1 of the lemma is proven. We now prove the second part of the lemma by induction on k. The base case in which k = K is trivial since s K ( p) ≤ t ( p). We inductively assume that the lemma holds at the beginning of iteration K − k + 1, and we prove it true at the end of iteration K − k + 1. As described at the beginning of this proof, let P be the set of flow paths that go through (vu, k − 1) at the beginning of iteration K − k + 1. Let p ∈ P originate from endnode i. At the end of iteration K − k + 1, it goes from i to v along p, then from v to w along (vw, k − 1) and finally from w to the core. The service charge of sending one unit of flow from i to w is at most (19)
s K ( p) + vw µk−1 ≤ t ( p) + 4t (q) ≤ 5t ( p).
If w is a core node, then we are done. Otherwise, a short path p1 goes from the leader node of j to the core via w at the beginning of iteration K − k + 1. (This is the same path p1 introduced earlier in this proof.) The path p then goes from w to the core along p1 . Let c5 be the service charge of sending one unit of demand from w to the core along p1 . We have (20)
c5 ≤ 5(K − k + 1)t (q1 ) = 5(K − k + 1) · 2s(q1 ) ≤ 5(K − k + 1) · 2g j ≤ 5(K − k + 1) · t ( p).
The first inequality holds by the third inductive hypothesis, the second holds since p1 is short, the third holds since q1 originates from the leader node of j and the last one holds by the definition of q. Adding up (19) and (20), we have sk−1 ( p) ≤ 5(K − k + 2)t ( p). The proof is complete. Part 1 of Lemma 14 proves that the third inductive hypothesis is maintained. Part 2 of Lemma 14 and condition 2 of Lemma 11 together imply
Approximation Algorithms for Access Network Design
COROLLARY 15. rounding.
215
The total service charge is O(K ) · OPT at the end of K iterations of
Combining Corollaries 13 and 15, we obtain the following. THEOREM 16. The rounding of LP-ACCESS gives a solution in which the total cost is O(K ) times the optimal.
References [1] [2]
[3] [4]
[5]
[6]
[7]
[8] [9] [10] [11]
[12]
[13]
B. Awerbuch and Y. Azar. Buy-at-bulk network design. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 542–547, Miami Beach, FL, October 1997. Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 184–193, Burlington, VT, October 1996. Y. Bartal. On approximating arbitrary metrics by tree metrics. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 161–168, Dallas, TX, May 1998. M. Charikar, C. Chekuri, A. Goel, and S. Guha. Rounding via trees: deterministic approximation algorithms for group steiner trees and k median. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 114–123, Dallas, TX, May 1998. M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. Approximating a finite metric by a small number of tree metrics. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, November 1998. M. Goemans and D. Williamson. The primal–dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-Hard Problems, D. Hochbaum, ed., pages 144–191, PWS, Boston, MA, 1995. K. Jain and V. Vazirani. Primal dual approximation algorithms for metric facility location and k-median problems. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 2–13, New York, October 1990. J. Lin and J. S. Vitter. ε-Approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 771–782, Victoria, B.C., May 1992. Y. Mansour and D. Peleg. An approximation algorithm for minimum-cost network design. Technical Report CS94-22, The Weizmann Institute of Science, Rehovot, 1994. A. Meyerson, K. Munagala, and S. Plotkin. Cost-distance: two metric network design. Technical Report STAN-CS-TN-00-92, Stanford University, Palo Alto, CA, 2000. F. S. Salman, J. Cheriyan, R. Ravi, and S. Subramanian. Buy at bulk network design: approximating the single-sink edge installation problem. In Proceedings of the 8th Annual ACM–SIAM Symposium on Discrete Algorithms, pages 619–628, New Orleans, LA, January 1997. D. B. Shmoys, E. Tardos, and K. Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 265–274, El Paso, TX, May 1997. A. Srinivasan and C. Teo. A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 636–643, El Paso, TX, May 1997.