Implementing approximation algorithms for the single-source unsplittable flow problem

ABSTRACT

In the single-source unsplittable flow problem, commodities must be routed simultaneously from a common source vertex to certain sinks in a given graph with edge capacities. The demand of each commodity must be routed along a single path so that the total flow through any edge is at most, its capacity. This problem was introduced by Kleinberg [1996a] and generalizes several NP-complete problems. A cost value per unit of flow may also be defined for every edge. In this paper, we implement the 2-approximation algorithm of Dinitz et al. [1999] for congestion, which is the best known, and the (3, 1)-approximation algorithm of Skutella [2002] for congestion and cost, which is the best known bicriteria approximation. We experimentally study the quality of approximation achieved by the algorithms and the effect of heuristics on their performance. We also compare these algorithms against the previous best ones by Kolliopoulos and Stein [1999].

REFERENCES

• 1: Ravindra K. Ahuja , Andrew V. Goldberg , James B. Orlin , Robert E. Tarjan, Finding minimum-cost flows by double scaling, Mathematical Programming: Series A and B, v.53 n.3, p.243-266, Feb. 1992 [doi>10.1007/BF01585705]
• 2: Badics, T. 1991. genrmf. ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf/.
• 3: Chandra S. Chekuri , Andrew V. Goldberg , David R. Karger , Matthew S. Levine , Cliff Stein, Experimental study of minimum cut algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.324-333, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: Andrew V. Goldberg, An efficient implementation of a scaling minimum-cost flow algorithm, Journal of Algorithms, v.22 n.1, p.1-29, Jan. 1997 [doi>10.1006/jagm.1995.0805]
• 5: Cherkassky, B. V. and Goldberg, A. V. 1997b. On implementing the push-relabel method for the maximum flow problem. Algorithmica 19, 390--410.
• 6: Dinitz, Y., Garg, N., and Goemans, M. X. 1999. On the single-source unsplittable flow problem. Combinatorica 19, 1--25.
• 7: Thomas Erlebach , Alexander Hall, NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.194-202, January 06-08, 2002, San Francisco, California
• 8: Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998 [doi>10.1145/290179.290181]
• 9: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 10: Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, Mathematics of Operations Research, v.15 n.3, p.430-466, Aug. 1990 [doi>10.1287/moor.15.3.430]
• 11: Goldfarb, D. and Grigoriadis, M. 1988. A computational comparison of the Dinic and Network Simplex methods for maximum flow. Annals of Operations Research 13, 83--123.
• 12: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 13: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 14: Kolliopoulos, S. G. Edge-disjoint paths and unsplittable flow. Handbook of Approximation Algorithms and Metaheuristics, T. F. Gonzalez, Ed. Chapman-Hall/CRC Press, to appear.
• 15: Stavros G. Kolliopoulos , Clifford Stein, Experimental Evaluation of Approximation Algorithms for Single-Source Unsplittable Flow, Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.328-344, June 09-11, 1999
• 16: Stavros G. Kolliopoulos , Clifford Stein, Approximation Algorithms for Single-Source Unsplittable Flow, SIAM Journal on Computing, v.31 n.3, p.919-946, 2001 [doi>10.1137/S0097539799355314]
• 17: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 18: Hiroshi Nagamochi , Tadashi Ono , Toshihide Ibaraki, Implementing an efficient minimum capacity cut algorithm, Mathematical Programming: Series A and B, v.67 n.3, p.325-341, Dec. 14, 1994 [doi>10.1007/BF01582226]
• 19: James B. Orlin, A faster strongly polynomial minimum cost flow algorithm, Operations Research, v.41 n.2, p.338-350, March–April 1993 [doi>10.1287/opre.41.2.338]
• 20: Skutella, M. 2002. Approximating the single-source unsplittable min-cost flow problem. Mathematical Programming B91, 3, 493--514.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Experimentation

Keywords:
Approximation algorithms, network flow, unsplittable flow