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 be a directed graph and let be source-sink pairs. We want to connect each pair by a path 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 for each pair where each path connects to . The goal is to choose, for each pair , one path from so as to minimize the maximum congestion on any edge. We can develop an integer programming formulation as follows. For each and each we have a variable which indicates whether we choose to route pair . The constraints express that exactly one path is for each pair . To minimize the maximum number of paths using any edge we introduce a variable and minimize it subject it to a natural packing constraint.
As usual we relax the integer constraints to obtain an LP relaxation where we replace with (in this particular case we can simply use 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 is explicitly given for each as part of the input.
Let 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 while we know that the optimum congestion is at least . Technically we should find the smallest integer such that the preceding LP is feasible. We will assume henceforth that 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 |
2. For |
3. Output |
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 no edge is contained in more than paths where is an absolute constant. Here are the number of edges in the graph . One can also show that for any fixed the congestion is at most with high probability.
Proof. The proof is a simple application of Chernoff-bounds and the union bound. Fix an edge . Let be the random variable which is the total number of paths in that use . Let be the binary random variable that indicates whether . Note that .
The first observation is that the variables are independent since we used independent randomness for the pairs. Second we claim that . Do you see why? Thus, by linearity of expectation,
where the last inequality follows from the LP constraint.
Since is the sum of independent binary valued random variables and we can apply Chernoff-bounds to estimate . Applying Corollary B.5 we conclude that we can choose such that this probability is at most . Now we apply the union bound over all edges and conclude that
Thus, with probability no edge is loaded to more that .
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 for concreteness. A success probability of the form where is the input size is typically called "with high probability".
Remark 7.2. The bound implies that when we obtain a constant factor approximation.
Remark 7.3. In a graph and hence one often sees the bounds expressed in terms of rather than . We chose to write in terms of rather than 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 and the pairs, and the goal is to choose one path for each pair from the set of all paths between and . In other words is an path in 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: for the pairs and for the edges. Thus, one is guaranteed, by the rank lemma that there is an optimum solution that has only 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 to so that the total flow on any edge is at most . We use variables to denote a flow for pair on edge .
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 we can take the one unit of flow and use standard flowdecomposition to obtain a path-flow with at most 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 in some fashion. For instance we can set to be the set of all paths in with at most edges for some given parameter . 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 [3]. In a remarkable result, [4] showed that 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 [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 and the pairs are constructed in a recursive fashion. Let be a parameter that we will fix later. We start with a directed path . We add a demand pair which connects to the path as follows. We partition the path into paths of equal length: add an arc to to the start of each sub-path and an arc from the end of each sub-path to . See figure.
One can see from the figure that the pair can splits its flow along paths. Now we consider each of the sub-paths and recursively create an instance on the path with length (while keeping parameter the same). Note that in the second level of the recursion we add new source-sink pairs, one for each sub-path. We stop the recursion when the size of the sub-path is . Let be the depth of the recursion.
We claim that there is a fractional routing of all demand pairs where the congestion is at most . This follows by splitting the flow of the pairs ways. The next claim is that some edge has congestion in any integral routing. This can be seen inductively. The top level pair has to choose one amongst the sub-paths - all edges in that sub-path will be used by the route for . Inductively there is some edge in that sub-path with congestion and hence the congestion of that edge will when we add the path for .
It now remains to set the parameters. If we choose say then . The fractional congestion is and integrally congestion is .
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 edges where is some given parameter. One can imagine that in many applications 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 . Thus, when 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 . 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 wishes to send one unit of flow. One can imagine a situation where one wants to send units of flow for pair where 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 paths for that each carry one unit of flow (the paths can overlap). This variant can be essentially reduced to the unit demand flow by creating copies of - we leave this as a simple exercise for the reader. The second variant is that we want each pair's flow of 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 and one wants to minimize congestion relative to . 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 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 resources . We have requests . Each request can be satisfied in ways let denote a collection of vectors . Each vector is an -dimensions: for each is a scalar that represents the load it induces on resource . The goal is to choose, for each , exactly one so as to minimize the maximum load on any resource. One can write this conveniently as the following integer program where we have variables for and which indicates whether chooses .
One can view the above integer program compactly as
where is a non-negative matrix with 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 if . We will assume that we have indeed done this.
One can do randomized rounding exactly as we did for Congestion Minimization and obtain an approximation. We say that is -column-sparse if the maximum number of non-zeroes in any column of is at most . This corresponds to paths in Congestion Minimization being allowed to have only edges. One can obtain an -approximation in this more general setting as well [8: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. ↩︎
- Prabhakar Raghavan. “Probabilistic construction of deterministic algorithms: approximating packing integer programs”. In: Journal of Computer and System Sciences 37.2 (1988), pp. 130–143. ↩︎
- 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. ↩︎
- 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. ↩︎
- 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. ↩︎
- 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. ↩︎
- Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, and Amit Kumar. “Approximation algorithms for the unsplittable flow problem”. In: Algorithmica 47.1 (2007), pp. 53–78. ↩︎
- Yefim Dinitz, Naveen Garg, and Michel X Goemans. “On the single-source unsplittable flow problem”. In: Combinatorica 19.1 (1999), pp. 17–41. ↩︎
- 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. ↩︎
- Sarah Morell and Martin Skutella. “Single source unsplittable flows with arc-wise lower and upper bounds”. In: Mathematical Programming (2021), pp. 1–20. ↩︎
- Martin Skutella. “A note on the ring loading problem”. In: SIAM Journal on Discrete Mathematics 30.1 (2016), pp. 327–342. ↩︎