Approximation Algorithms: Congestion Minimization in Networks

This is the lecture notes from Chandra Chekuri's CS583 course on Approximation Algorithms. Chapter 7: Congestion Minimization in Networks. You can read Chapter 8: Introduction to Local Search, here. Chapter 6: Unrelated Machine Scheduling and Generalized Assignment, here.
Chapter 7
In Chapter 6 we saw the Scheduling on Unrelated Parallel Machines problem. Here we consider two problems that also consider allocation with the objective of minimizing load/congestion. We will first consider the Congestion Minimization problem in graphs and then the abstract problem of Min-Max-Integer-Programs.

7.1 Congestion Minimization and VLSI Routing

A classical routing problem that was partly inspired by VLSI (very large scale integrated) circuit design is the following. Let G = ( V , E ) G = ( V , E ) G=(V,E)G=(V, E) be a directed graph and let ( s 1 , t 1 ) , , ( s k , t k ) s 1 , t 1 , , s k , t k (s_(1),t_(1)),dots,(s_(k),t_(k))\left(s_{1}, t_{1}\right), \ldots,\left(s_{k}, t_{k}\right) be k k kk source-sink pairs. We want to connect each pair ( s i , t i ) s i , t i (s_(i),t_(i))\left(s_{i}, t_{i}\right) by a path P i P i P_(i)P_{i} such that the paths do not share edges (or nodes). Alternatively we would like to minimize the maximum number of paths that use any edge - this is called the Congestion Minimization problem. A special case is EDP which is to decide if there are paths for the pairs that are edge-disjoint (NDP is the version where the paths are required to be node-disjoint). EDP and NDP are classical NP-Complete problems and have many important connections to multicommodity flows, routing, cuts, and graph theory. Thus Congestion Minimization is an NP-Hard optimization problem. Here we will consider two variants.
Choosing one path from a given collection: We consider a conceptually simpler variant where we are given a finite path collection P i P i P_(i)\mathcal{P}_{i} for each pair ( s i , t i ) s i , t i (s_(i),t_(i))\left(s_{i}, t_{i}\right) where each path P P i P P i P inP_(i)P \in \mathcal{P}_{i} connects s i s i s_(i)s_{i} to t i t i t_(i)t_{i}. The goal is to choose, for each pair ( s i , t i ) s i , t i (s_(i),t_(i))\left(s_{i}, t_{i}\right), one path from P i P i P_(i)\mathcal{P}_{i} so as to minimize the maximum congestion on any edge. We can develop an integer programming formulation as follows. For each i i ii and each P P i P P i P inP_(i)P \in \mathcal{P}_{i} we have a variable x i , P x i , P x_(i,P)x_{i, P} which indicates whether we choose P P PP to route pair i i ii. The constraints express that exactly one path is for each pair i i ii. To minimize the maximum number of paths using any edge we introduce a variable λ λ lambda\lambda and minimize it subject it to a natural packing constraint.
minimize λ subject to P P i x i , P = 1 1 i k i = 1 k P P i , P e x i , P λ e E x i , P λ 1 i k , P P i minimize λ subject to P P i x i , P = 1 1 i k i = 1 k P P i , P e x i , P λ e E x i , P λ 1 i k , P P i {:["minimize"qquadlambda],["subject to"qquadsum_(P inP_(i))x_(i,P)=1qquadqquadqquad1 <= i <= k],[sum_(i=1)^(k)sum_(P inP_(i),P_(∋e))x_(i,P) <= lambdaAA e in E],[x_(i,P) <= lambda1 <= i <= k","P inP_(i)]:}\begin{aligned} \text{minimize}\qquad&\lambda &\\ \text{subject to}\qquad&\sum_{P \in \mathcal{P}_{i}} x_{i, P}=1\qquad\qquad\qquad& 1 \leq i \leq k\\ &\sum_{i=1}^{k} \sum_{P \in \mathcal{P}_{i}, P_{\ni e}} x_{i, P} \leq \lambda & \forall e \in E\\ &x_{i, P} \leq \lambda& 1 \leq i \leq k, P \in \mathcal{P}_{i} \end{aligned}
As usual we relax the integer constraints to obtain an LP relaxation where we replace x i , P { 0 , 1 } x i , P { 0 , 1 } x_(i,P)in{0,1}x_{i, P} \in\{0,1\} with x i , P [ 0 , 1 ] x i , P [ 0 , 1 ] x_(i,P)in[0,1]x_{i, P} \in[0,1] (in this particular case we can simply use x i , P 0 x i , P 0 x_(i,P) >= 0x_{i, P} \geq 0 due to the other constraints). Note the similarities with the IP/LP for Scheduling on Unrelated Parallel Machines. The LP relaxation is of size polynomial in the input size since the path collection P i P i P_(i)\mathcal{P}_{i} is explicitly given for each i i ii as part of the input.
Let λ λ lambda^(**)\lambda^{*} be the optimum LP solution value. There is a technicality that arises just as we saw with Scheduling on Unrelated Parallel Machines. It may happen that λ < 1 λ < 1 lambda** < 1\lambda *<1 while we know that the optimum congestion is at least 1 1 11. Technically we should find the smallest integer λ λ lambda^(**)\lambda^{*} such that the preceding LP is feasible. We will assume henceforth that λ λ lambda^(**)\lambda^{*} is an integer.
How do we round? A simple stragegy is randomized rounding. In fact the technique of randomized rounding and analysis via Chernoff bounds was developed in the influential paper of Raghavan and Thompson [1] precisely for this problem!
Randomized-Rounding
1. Solve LP relaxation and find optimum solution x , λ x , λ x^(**),lambda^(**)x^{*}, \lambda^{*}.
2. For i = 1 i = 1 i=1i=1 to k k kk do
quad\quad A. Pick exactly one path Q i P i Q i P i Q_(i)inP_(i)Q_{i} \in \mathcal{P}_{i} randomly where the probability of
qquad\qquad picking P P PP is exactly x i , P x i , P x_(i,P)^(**)x_{i, P}^{*}.
3. Output Q 1 , Q 2 , , Q k Q 1 , Q 2 , , Q k Q_(1),Q_(2),dots,Q_(k)Q_{1}, Q_{2}, \ldots, Q_{k}.
Note that the choices for the pairs done with independent randomness. The analysis requires the use of Chernoff-Hoeffding bounds. See Chapter B.
Theorem 7.1. Randomized rounding outputs one path per pair and with probability at least ( 1 1 / m 2 ) 1 1 / m 2 (1-1//m^(2))\left(1-1 / m^{2}\right) no edge is contained in more than c log m log log m λ c log m log log m λ c(log m)/(log log m)*lambda^(**)c \frac{\log m}{\log \log m} \cdot \lambda^{*} paths where c c cc is an absolute constant. Here m m mm are the number of edges in the graph G G GG. One can also show that for any fixed ϵ > 0 ϵ > 0 epsilon > 0\epsilon>0 the congestion is at most ( 1 + ϵ ) λ + c log m ϵ 2 ( 1 + ϵ ) λ + c log m ϵ 2 (1+epsilon)lambda^(**)+c(log m)/(epsilon^(2))(1+\epsilon) \lambda^{*}+c \frac{\log m}{\epsilon^{2}} with high probability.
Proof. The proof is a simple application of Chernoff-bounds and the union bound. Fix an edge e E e E e in Ee \in E. Let Y e Y e Y_(e)Y_{e} be the random variable which is the total number of paths in Q 1 , Q 2 , , Q k Q 1 , Q 2 , , Q k Q_(1),Q_(2),dots,Q_(k)Q_{1}, Q_{2}, \ldots, Q_{k} that use e e ee. Let Y e , i Y e , i Y_(e,i)Y_{e, i} be the binary random variable that indicates whether e Q i e Q i e inQ_(i)e \in Q_{i}. Note that Y e = i = 1 k Y e , i Y e = i = 1 k Y e , i Y_(e)=sum_(i=1)^(k)Y_(e,i)Y_{e}=\sum_{i=1}^{k} Y_{e, i}.
The first observation is that the variables Y e , 1 , Y e , 2 , , Y e , k Y e , 1 , Y e , 2 , , Y e , k Y_(e,1),Y_(e,2),dots,Y_(e,k)Y_{e, 1}, Y_{e, 2}, \ldots, Y_{e, k} are independent since we used independent randomness for the pairs. Second we claim that E [ Y e , i ] = P [ Y e , i = 1 ] = P P i , e P x i , P E Y e , i = P Y e , i = 1 = P P i , e P x i , P E[Y_(e,i)]=P[Y_(e,i)=1]=sum_(P inP_(i),e in P)x_(i,P)^(**)\mathbf{E}\left[Y_{e, i}\right]=\mathbf{P}\left[Y_{e, i}=1\right]=\sum_{P \in \mathcal{P}_{i}, e \in P} x_{i, P}^{*}. Do you see why? Thus, by linearity of expectation,
E [ Y e ] = i E [ Y e , i ] = i P P i , e P x i , P λ E Y e = i E Y e , i = i P P i , e P x i , P λ E[Y_(e)]=sum_(i)E[Y_(e,i)]=sum_(i)sum_(P inP_(i),e in P)x_(i,P)^(**) <= lambda^(**)\mathbf{E}\left[Y_{e}\right]=\sum_{i} \mathbf{E}\left[Y_{e, i}\right]=\sum_{i} \sum_{P \in \mathcal{P}_{i}, e \in P} x_{i, P}^{*} \leq \lambda^{*}
where the last inequality follows from the LP constraint.
Since Y e Y e Y_(e)Y_{e} is the sum of independent binary valued random variables and E [ Y e ] λ E [ Y e ] λ E[Y_(e)] <= lambda^(**)\mathbf{E}[Y_{e}] \leq \lambda^{*} we can apply Chernoff-bounds to estimate P [ Y e c log m log log m λ ] P [ Y e c log m log log m λ ] P[Y_(e) >= c(log m)/(log log m)lambda^(**)]\mathbf{P}[Y_{e} \geq c \frac{\log m}{\log \log m} \lambda^{*}]. Applying Corollary B.5 we conclude that we can choose c c cc such that this probability is at most 1 / m 3 1 / m 3 1//m^(3)1 / \mathrm{m}^{3}. Now we apply the union bound over all edges and conclude that
P [ e E , Y e c log m log log m λ ] m / m 3 1 / m 2 . P [ e E , Y e c log m log log m λ ] m / m 3 1 / m 2 . P[EE e in E,Y_(e) >= c(log m)/(log log m)lambda^(**)] <= m//m^(3) <= 1//m^(2).\mathbf{P}[\exists e \in E, Y_{e} \geq c \frac{\log m}{\log \log m} \lambda^{*}] \leq m / m^{3} \leq 1 / m^{2} .
Thus, with probability 1 1 / m 2 1 1 / m 2 >= 1-1//m^(2)\geq 1-1 / m^{2} no edge is loaded to more that c log m log log m λ c log m log log m λ c(log m)/(log log m)lambda^(**)c \frac{\log m}{\log \log m} \lambda^{*}.
The second bound can be derived in the same way by using the second Chernoff-bound in Corollary B.5.
Remark 7.1. We chose the bound ( 1 1 / m 2 ) 1 1 / m 2 (1-1//m^(2))\left(1-1 / \mathrm{m}^{2}\right) for concreteness. A success probability of the form ( 1 1 / poly ( n ) ) ( 1 1 / poly ( n ) ) (1-1//poly(n))(1-1 /\operatorname{poly}(n)) where n n nn is the input size is typically called "with high probability".
Remark 7.2. The bound ( 1 + ϵ ) λ + c log m / ϵ 2 ( 1 + ϵ ) λ + c log m / ϵ 2 (1+epsilon)lambda^(**)+c log m//epsilon^(2)(1+\epsilon) \lambda^{*}+c \log m / \epsilon^{2} implies that when λ c log m λ c log m lambda^(**) >= c log m\lambda^{*} \geq c \log m we obtain a constant factor approximation.
Remark 7.3. In a graph m = O ( n 2 ) m = O n 2 m=O(n^(2))m=O\left(n^{2}\right) and hence one often sees the bounds expressed in terms of n n nn rather than m m mm. We chose to write in terms of m m mm rather than n n nn to highlight the fact that the bound depends on the number of constraints via the union bound. We will discuss later how column sparsity based bounds can give refined results that avoid the union bound.
Implicitly given path collections: In the traditional version of Congestion Minimization we are only given G G GG and the pairs, and the goal is to choose one path P P PP for each ( s i , t i ) s i , t i (s_(i),t_(i))\left(s_{i}, t_{i}\right) pair from the set of all paths between s i s i s_(i)s_{i} and t i t i t_(i)t_{i}. In other words P i = { P P P i = P P P_(i)={P∣P:}\mathcal{P}_{i}=\left\{P \mid P\right. is an s i t i s i t i s_(i)-t_(i)s_{i}-t_{i} path in G } . P i G . P i {:G}.P_(i)\left.G\right\} . \mathcal{P}_{i} is implicity defined and its size can be exponential in the graph size. It is not obvious that we can solve the LP relaxation that we saw above. However, one can indeed solve it in polynomialtime via the Ellipsoid method. First, we observe that the LP could have an exponential number of variables but only a polynomial number of non-trivial constraints: k k kk for the pairs and m m mm for the edges. Thus, one is guaranteed, by the rank lemma that there is an optimum solution that has only k + m k + m k+mk+m non-zero variables To see that one can indeed find it efficiently, we need to look at the dual and notice that the separation oracle for the dual is the shortest path problem.
Another way to see that the LP can solved is by writing a compact formulation via the well-known multicommodity flow. We want to send one unit of flow from s i s i s_(i)s_{i} to t i t i t_(i)t_{i} so that the total flow on any edge is at most λ λ lambda\lambda. We use variables f ( e , i ) f ( e , i ) f(e,i)f(e, i) to denote a flow for pair i i ii on edge e e ee.
minimize λ subject to e δ + ( s i ) f ( e , i ) e δ ( s i ) f ( e , i ) = 1 1 i k e δ + ( v ) f ( e , i ) e δ ( v ) f ( e , i ) = 0 1 i k , v V { s i , t i } i = 1 k f ( e , i ) λ e E f ( e , i ) 0 1 i k , e E minimize λ subject to e δ + s i f ( e , i ) e δ s i f ( e , i ) = 1 1 i k e δ + ( v ) f ( e , i ) e δ ( v ) f ( e , i ) = 0 1 i k , v V s i , t i i = 1 k f ( e , i ) λ e E f ( e , i ) 0 1 i k , e E {:["minimize"qquadlambda],["subject to"qquadsum_(e indelta^(+)(s_(i)))f(e","i)-sum_(e indelta^(-)(s_(i)))f(e","i)=1qquad1 <= i <= k],[sum_(e indelta^(+)(v))f(e","i)-sum_(e indelta^(-)(v))f(e","i)=01 <= i <= k","v in V-{s_(i),t_(i)}],[sum_(i=1)^(k)f(e","i) <= lambdaAA e in E],[f(e","i) >= 01 <= i <= k","e in E]:}\begin{aligned} \text{minimize}\qquad& \lambda & \\ \text{subject to} \qquad& \sum_{e \in \delta^{+}\left(s_{i}\right)} f(e, i)-\sum_{e \in \delta^{-}\left(s_{i}\right)} f(e, i)=1\qquad& 1 \leq i \leq k \\ & \sum_{e \in \delta^{+}(v)} f(e, i)-\sum_{e \in \delta^{-}(v)} f(e, i)=0 & 1 \leq i \leq k, v \in V-\left\{s_{i}, t_{i}\right\} \\ &\sum_{i=1}^{k} f(e, i) \leq \lambda & \forall e \in E\\ &f(e, i) \geq 0 & 1 \leq i \leq k, e \in E \end{aligned}
The preceding multicommodity flow LP has a polynomial number of variables and can be solved in polynomial-time. Given a flow, for each commodity/pair i i ii we can take the one unit of s i t i s i t i s_(i)-t_(i)s_{i}-t_{i} flow and use standard flowdecomposition to obtain a path-flow with at most m m mm paths in the collection. We can then apply the rounding that we saw above with an given explicit path collection in exactly the same way.
Remark 7.4. The Ellipsoid based algorithm may seem impractical. However, one can approximately solve the implicit path based LP via multiplicative weight update methods efficiently. The implicit formulation and Ellipsoid method is also useful when one may want to restrict P i P i P_(i)\mathcal{P}_{i} in some fashion. For instance we can set P i P i P_(i)\mathcal{P}_{i} to be the set of all s i t i s i t i s_(i)-t_(i)s_{i}-t_{i} paths in G G GG with at most d d dd edges for some given parameter d d dd. This will ensure that we choose only "short" paths for each pair. It is not hard to see that the separation oracle for the dual is another shortest path type problem that can be solved efficiently (via Bellman-Ford type algorithm). This is not easy to capture/see via the compact flow based formulation.
Derandomization: Is there a deterministic algorithm with the roughly the same approximation guarantee? The algorithm can be derandomized via the notion of pessimistic estimators. Congestion Minimization was one of the first instances with a sophisticated use of this technique [2].
Integrality gap and Hardness of Approximation: There is simple yet clever example demonstrating that the integrality gap of the flow relaxation in directed graphs is Ω ( log m / log log m ) Ω ( log m / log log m ) Omega(log m//log log m)\Omega(\log m / \log \log m) [3]. In a remarkable result, [4] showed that O ( log m / log log m ) O ( log m / log log m ) O(log m//log log m)O(\log m / \log \log m) is the hardness factor. The complexity of Congestion Minimization is less clear in undirected graphs. It is known that the LP integrality gap and hardness of approximation are Ω ( log log n / log log log n ) Ω ( log log n / log log log n ) Omega(log log n//log log log n)\Omega(\log \log n / \log \log \log n) [5]. Closing the gap betten the upper and lower bounds is a major open problem.
Here we outline the integrality gap example for directed graphs from [3:1]. The graph G G GG and the pairs are constructed in a recursive fashion. Let h h hh be a parameter that we will fix later. We start with a directed path v 0 , v 1 , , v n v 0 , v 1 , , v n v_(0),v_(1),dots,v_(n)v_{0}, v_{1}, \ldots, v_{n}. We add a demand pair ( s 1 , t 1 ) s 1 , t 1 (s_(1),t_(1))\left(s_{1}, t_{1}\right) which connects to the path as follows. We partition the path into n / h n / h n//hn / h paths of equal length: add an arc to s s ss to the start of each sub-path and an arc from the end of each sub-path to t t tt. See figure.
One can see from the figure that the pair ( s , t ) ( s , t ) (s,t)(s, t) can splits its flow along h h hh paths. Now we consider each of the h h hh sub-paths and recursively create an instance on the path with length n / h 1 n / h 1 n//h-1n / h-1 (while keeping parameter h h hh the same). Note that in the second level of the recursion we add h h hh new source-sink pairs, one for each sub-path. We stop the recursion when the size of the sub-path is Θ ( h ) Θ ( h ) Theta(h)\Theta(h). Let d d dd be the depth of the recursion.
We claim that there is a fractional routing of all demand pairs where the congestion is at most d / h d / h d//hd / h. This follows by splitting the flow of the pairs h h hh ways. The next claim is that some edge has congestion d d dd in any integral routing. This can be seen inductively. The top level pair ( s , t ) ( s , t ) (s,t)(s, t) has to choose one amongst the h h hh sub-paths - all edges in that sub-path will be used by the route for ( s , t ) ( s , t ) (s,t)(s, t). Inductively there is some edge in that sub-path with congestion d 1 d 1 d-1d-1 and hence the congestion of that edge will d d dd when we add the path for ( s , t ) ( s , t ) (s,t)(s, t).
It now remains to set the parameters. If we choose h = log 2 n h = log 2 n h=log^(2)nh=\log ^{2} n say then d = Θ ( log n / log log n ) d = Θ ( log n / log log n ) d=Theta(log n//log log n)d=\Theta(\log n / \log \log n). The fractional congestion is 1 1 <= 1\leq 1 and integrally congestion is Θ ( log n / log log n ) Θ ( log n / log log n ) Theta(log n//log log n)\Theta(\log n / \log \log n).
Short paths and improved congestion via Lovász-Local-Lemma: We consider the congestion minimization problem when the path for each pair is required to be "short". By this we mean that we are required to route on a path with at most d d dd edges where d d dd is some given parameter. One can imagine that in many applications d d dd is small and is a fixed constant, say 10. The question is whether the approximation ratio can be improved. Indeed one can show that the LP integrality gap is O ( log d / log log d ) O ( log d / log log d ) O(log d//log log d)O(\log d / \log \log d). Thus, when d n d n d≪nd \ll n we get a substantial improvement. However, proving this and obtaining a polynomial time algorithm are quite non-trivial. One requires the use of the subtle LovászLocal-Lemma (LLL), a powerful tool in probabilistic combinatorics. Typically LLL only gives a proof of existence and there was substantial work in making LLL constructive/efficient. Srinivasan obtained an algorithm via derandomization of LLL in this context with a lot of technical work [6]. There was a breakthrough work of Moser and Tardos [7] that gave an extremely simple way to make LLL constructive and this has been refined and developed over the last decade. For the congestion minimization problem we refer the reader to [8] which builds upon [7:1] and describes an efficient randomized algorithm that outputs a solution with congestion O ( log d / log log d ) O ( log d / log log d ) O(log d//log log d)O(\log d / \log \log d). In fact the application is given in the context of a more abstract problem that we discuss in the next section.
Integer flows and Unsplittable flows: We worked with the simple setting where each pair ( s i , t i ) s i , t i (s_(i),t_(i))\left(s_{i}, t_{i}\right) wishes to send one unit of flow. One can imagine a situation where one wants to send d i d i d_(i)d_{i} units of flow for pair i i ii where d i d i d_(i)d_{i} is some (integer) demand value. There are two interesting variants. The first one requires integer valued flow for each pair which means that we want to find d i d i d_(i)d_{i} paths for ( s i , t i ) s i , t i (s_(i),t_(i))\left(s_{i}, t_{i}\right) that each carry one unit of flow (the paths can overlap). This variant can be essentially reduced to the unit demand flow by creating d i d i d_(i)d_{i} copies of ( s i , t i ) s i , t i (s_(i),t_(i))\left(s_{i}, t_{i}\right) - we leave this as a simple exercise for the reader. The second variant is that we want each pair's flow of d i d i d_(i)d_{i} units to be sent along a single path - this is called unsplittable flow. When discussing unsplittable flow it is also natural to consider capacities on the edges. Thus, each edge has a capacity u e u e u_(e)u_{e} and one wants to minimize congestion relative to u e u e u_(e)u_{e}. The techniques we discussed can be generalized relatively easily to this version as well to obtain the same kind of bounds. The unsplittable flow problem is interesting even in the setting where there is a single source/sink or when the graph is a simple ring or a path. Interesting results are known here and we refer the reader to [9] [10] [11] [12] [13] [14] for further pointers.

7.2 Min-max Integer Programs

If one looks at the rounding and analysis for Congestion Minimization we notice that the algorithm uses very little about the structure of the graph. This can be thought about in two ways. One is that perhaps we can do better by exploiting graph structure. Two, we can abstract the problem into a more general class where the same technique applies. As we mentioned, in directed graphs the bound of O ( log n / log log n ) O ( log n / log log n ) O(log n//log log n)O(\log n / \log \log n) is tight but the bound may not be tight in undirected graphs which admit more structure.
Here we consider the second point and develop a resource allocation view point while making an analogy to Congestion Minimization so that the abstract problem can be more easily understood. Suppose we have m m mm resources e 1 , e 2 , , e m e 1 , e 2 , , e m e_(1),e_(2),dots,e_(m)e_{1}, e_{2}, \ldots, e_{m}. We have k k kk requests r 1 , r 2 , , r k r 1 , r 2 , , r k r_(1),r_(2),dots,r_(k)r_{1}, r_{2}, \ldots, r_{k}. Each request i i ii can be satisfied in i i ℓ_(i)\ell_{i} ways -- let P i P i P_(i)\mathcal{P}_{i} denote a collection of i i ℓ_(i)\ell_{i} vectors v i , 1 , v i , 2 , , v i , i v i , 1 , v i , 2 , , v i , i v_(i,1),v_(i,2),dots,v_(i,ℓ_(i))v_{i, 1}, v_{i, 2}, \ldots, v_{i, \ell_{i}}. Each vector v i , j P i v i , j P i v_(i,j)inP_(i)v_{i, j} \in \mathcal{P}_{i} is an m m mm-dimensions: for each k [ m ] , v i , j , k k [ m ] , v i , j , k k in[m],v_(i,j,k)k \in[m], v_{i, j, k} is a scalar that represents the load it induces on resource e k e k e_(k)e_{k}. The goal is to choose, for each i i ii, exactly one j [ i ] j i j in[ℓ_(i)]j \in\left[\ell_{i}\right] so as to minimize the maximum load on any resource. One can write this conveniently as the following integer program where we have variables x i , j x i , j x_(i,j)x_{i, j} for 1 i k 1 i k 1 <= i <= k1 \leq i \leq k and 1 j i 1 j i 1 <= j <= ℓ_(i)1 \leq j \leq \ell_{i} which indicates whether i i ii chooses j j jj.
minimize λ subject to 1 j i x i , j = 1 1 i k i = 1 k 1 j i v i , j , k x i , j λ e k x i , j { 0 , 1 } 1 i k , 1 j i minimize λ subject to 1 j i x i , j = 1 1 i k i = 1 k 1 j i v i , j , k x i , j λ e k x i , j { 0 , 1 } 1 i k , 1 j i {:["minimize"qquadlambda],["subject to"qquadsum_(1 <= j <= ℓ_(i))x_(i,j)=1qquad1 <= i <= k],[sum_(i=1)^(k)sum_(1 <= j <= ℓ_(i))v_(i,j,k)x_(i,j) <= lambdaAAe_(k)],[x_(i,j)in{0","1}1 <= i <= k","1 <= j <= ℓ_(i)]:}\begin{aligned} \text{minimize}\qquad& \lambda & \\ \text{subject to} \qquad& \sum_{1 \leq j \leq \ell_{i}} x_{i, j}=1\qquad& 1 \leq i \leq k \\ & \sum_{i=1}^{k} \sum_{1 \leq j \leq \ell_{i}} v_{i, j, k} x_{i, j} \leq \lambda & \forall e_{k} \\ &x_{i, j} \in\{0,1\} & 1 \leq i \leq k, 1 \leq j \leq \ell_{i} \end{aligned}
One can view the above integer program compactly as
minimize λ subject to 1 j i x i , j = 1 1 i k A x λ 1 x i , j { 0 , 1 } 1 i k , 1 j i minimize λ subject to 1 j i x i , j = 1 1 i k A x λ 1 x i , j { 0 , 1 } 1 i k , 1 j i {:["minimize"qquadlambda],["subject to"qquadsum_(1 <= j <= ℓ_(i))x_(i,j)=1qquad1 <= i <= k],[Ax <= lambda1],[x_(i,j)in{0","1}1 <= i <= k","1 <= j <= ℓ_(i)]:}\begin{aligned} \text{minimize}\qquad& \lambda & \\ \text{subject to} \qquad& \sum_{1 \leq j \leq \ell_{i}} x_{i, j}=1\qquad& 1 \leq i \leq k \\ &A x \leq \lambda \mathbb{1} &\\ &x_{i, j} \in\{0,1\} & 1 \leq i \leq k, 1 \leq j \leq \ell_{i} \end{aligned}
where A A AA is a non-negative matrix with m m mm rows. As with Scheduling on Unrelated Parallel Machines we need to be careful when relaxing the IP to an LP since the optimum solution to the LP can be a poor lower bound unless we ensure that x i , j = 0 x i , j = 0 x_(i,j)=0x_{i, j}=0 if v i , j , k > λ v i , j , k > λ v_(i,j,k) > lambdav_{i, j, k}>\lambda. We will assume that we have indeed done this.
One can do randomized rounding exactly as we did for Congestion Minimization and obtain an O ( log m / log log m ) O ( log m / log log m ) O(log m//log log m)O(\log m / \log \log m) approximation. We say that A A AA is d d dd-column-sparse if the maximum number of non-zeroes in any column of A A AA is at most d d dd. This corresponds to paths in Congestion Minimization being allowed to have only d d dd edges. One can obtain an O ( log d / log log d ) O ( log d / log log d ) O(log d//log log d)O(\log d / \log \log d)-approximation in this more general setting as well [8:1].

  1. Prabhakar Raghavan and Clark D Tompson. “Randomized rounding: a technique for provably good algorithms and algorithmic proofs”. In: Combinatorica 7.4 (1987), pp. 365–374. ↩︎
  2. Prabhakar Raghavan. “Probabilistic construction of deterministic algorithms: approximating packing integer programs”. In: Journal of Computer and System Sciences 37.2 (1988), pp. 130–143. ↩︎
  3. Tom Leighton, Satish Rao, and Aravind Srinivasan. “Multicommodity flow and circuit switching”. In: Proceedings of the Thirty-First Hawaii International Conference on System Sciences. Vol. 7. IEEE. 1998, pp. 459–465. ↩︎ ↩︎
  4. Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, and Kunal Talwar. “Hardness of Routing with Congestion in Directed Graphs”. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. STOC ’07. San Diego, California, USA: Association for Computing Machinery, 2007, pp. 165–178. isbn: 9781595936318. doi: 10. 1145/1250790.1250816. url: https://doi.org/10.1145/1250790.1250816. ↩︎
  5. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, and Lisa Zhang. “Inapproximability of edgedisjoint paths and low congestion routing on undirected graphs”. In: Combinatorica 30.5 (2010), pp. 485–520. ↩︎
  6. Aravind Srinivasan. “An extension of the Lovász Local Lemma, and its applications to integer programming”. In: SIAM Journal on Computing 36.3 (2006), pp. 609–634. ↩︎
  7. Robin A Moser and Gábor Tardos. “A constructive proof of the general Lovász local lemma”. In: Journal of the ACM (JACM) 57.2 (2010), pp. 1–15. ↩︎ ↩︎
  8. Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. “New constructive aspects of the Lovász local lemma”. In: Journal of the ACM (JACM) 58.6 (2011), pp. 1–28. ↩︎ ↩︎
  9. Anna Adamaszek, Parinya Chalermsook, Alina Ene, and Andreas Wiese. “Submodular unsplittable flow on trees”. In: International Conference on Integer Programming and Combinatorial Optimization. Springer. 2016, pp. 337–349. ↩︎
  10. Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, and Amit Kumar. “Approximation algorithms for the unsplittable flow problem”. In: Algorithmica 47.1 (2007), pp. 53–78. ↩︎
  11. Yefim Dinitz, Naveen Garg, and Michel X Goemans. “On the single-source unsplittable flow problem”. In: Combinatorica 19.1 (1999), pp. 17–41. ↩︎
  12. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. “A (5/3+ 휀)-approximation for unsplittable flow on a path: placing small tasks into boxes”. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018, pp. 607–619. ↩︎
  13. Sarah Morell and Martin Skutella. “Single source unsplittable flows with arc-wise lower and upper bounds”. In: Mathematical Programming (2021), pp. 1–20. ↩︎
  14. Martin Skutella. “A note on the ring loading problem”. In: SIAM Journal on Discrete Mathematics 30.1 (2016), pp. 327–342. ↩︎

Recommended for you

Jintang Li
Adversarial Learning on Graph
Adversarial Learning on Graph
This review gives an introduction to Adversarial Machine Learning on graph-structured data, including several recent papers and research ideas in this field. This review is based on our paper “A Survey of Adversarial Learning on Graph”.
7 points
0 issues