article

Implementing approximation algorithms for the single-source unsplittable flow problem

Authors:

Stavros G. KolliopoulosAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 10

Pages 2.3 - es

https://doi.org/10.1145/1064546.1180614

Published: 31 December 2005 Publication History

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]

Ahuja, R. K., Goldberg, A. V., Orlin, J. B., and Tarjan, R. E. 1992. Finding Minimum-Cost Flows by Double Scaling. Mathematical Programming 53, 243--266.]]

Digital Library

[2]

Badics, T. 1991. genrmf. ftp://dimacs.rutgers.edu/pub/netflow/generators/network/genrmf/.]]

[3]

Chekuri, C., Goldberg, A. V., Karger, D., Levine, M., and Stein, C. 1997. Experimental study of minimum cut algorithms. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. 324--333.]]

Digital Library

[4]

Cherkassky, B. V. and Goldberg, A. V. 1997a. An efficient implementation of a scaling minimum-cost flow algorithm. Journal of Algorithms 22, 1--29.]]

Digital Library

[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]

Erlebach, T. and Hall, A. 2002. NP-hardness of broadcast sheduling and inapproximability of single-source unsplittable min-cost flow. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms. 194--202.]]

Digital Library

[8]

Goldberg, A. V. and Rao, S. 1998. Beyond the flow decomposition barrier. Journal of the ACM 45, 783--797.]]

Digital Library

[9]

Goldberg, A. V. and Tarjan, R. E. 1988. A new approach to the maximum flow problem. Journal of the ACM 35, 4 (Oct.), 921--940.]]

Digital Library

[10]

Goldberg, A. V. and Tarjan, R. E. 1990. Solving minimum-cost flow problems by successive approximation. Mathematics of Operations Research 15, 3, 430--466.]]

Digital Library

[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]

Kleinberg, J. M. 1996a. Approximation algorithms for disjoint paths problems. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA.]]

Digital Library

[13]

Kleinberg, J. M. 1996b. Single-source unsplittable flow. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. 68--77.]]

Digital Library

[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]

Kolliopoulos, S. G. and Stein, C. 1999. Experimental evaluation of approximation algorithms for single-source unsplittable flow. In Proceedings of the 7th Integer Programming and Combinatorial Optimization Conference, LNCS. vol. 1610. Springer-Verlag, New York. 153--168.]]

Digital Library

[16]

Kolliopoulos, S. G. and Stein, C. 2002. Approximation algorithms for single-source unsplittable flow. SIAM J. Computing 31, 3, 919--946.]]

Digital Library

[17]

Lenstra, J. K., Shmoys, D. B., and Tardos, E. 1990. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming 46, 259--271. Preliminary version in Proc. FOCS 1987.]]

Digital Library

[18]

Nagamochi, H., Ono, T., and Ibaraki, T. 1994. Implementing an efficient minimum capacity cut algorithm. Mathematical Programming 67, 325--241.]]

Digital Library

[19]

Orlin, J. B. 1993. A faster strongly polynomial minimum cost flow algorithm. Operations Research 41, 338--350.]]

Digital Library

[20]

Skutella, M. 2002. Approximating the single-source unsplittable min-cost flow problem. Mathematical Programming B91, 3, 493--514.]]

Digital Library

Cited By

Morell SSkutella M(2020)Single Source Unsplittable Flows with Arc-Wise Lower and Upper BoundsInteger Programming and Combinatorial Optimization10.1007/978-3-030-45771-6_23(294-306)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-45771-6_23
Cohen RLewin-Eytan LSeffi Naor JRaz D(2013)Almost optimal virtual machine placement for traffic intense data centers2013 Proceedings IEEE INFOCOM10.1109/INFCOM.2013.6566794(355-359)Online publication date: Apr-2013
https://doi.org/10.1109/INFCOM.2013.6566794
Martens MSalazar FSkutella M(2007)Convex combinations of single source unsplittable flowsProceedings of the 15th annual European conference on Algorithms10.5555/1778580.1778618(395-406)Online publication date: 8-Oct-2007
https://dl.acm.org/doi/10.5555/1778580.1778618
Show More Cited By

Index Terms

Implementing approximation algorithms for the single-source unsplittable flow problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

Approximation Algorithms for Single-Source Unsplittable Flow

In the single-source unsplittable flow problem, we are given a network G, a source vertex s, and k commodities with sinks t_i and real-valued demands $\rho_i,$ $1\leq i \leq k.$ We seek to route the demand $\rho_i$ of each commodity i along a single s-t_i ...
On the Single-Source Unsplittable Flow Problem
FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science

Let $G=(V,E)$ be a capacitated directed graph with a source $s$ and $k$ terminals $t_i$ with demands $d_i$, $1\le i\le k$. We would like to concurrently route every demand on a single path from $s$ to the corresponding terminal without violating the ...
The k-Splittable Flow Problem

In traditional multi-commodity flow theory, the task is to send a certain amount of each commodity from its start to its target node, subject to capacity constraints on the edges. However, no restriction is imposed on the number of paths used for ...

Comments

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 10, Issue

2005

291 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/1064546

Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 December 2005

Published in JEA Volume 10

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
442
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Morell SSkutella M(2020)Single Source Unsplittable Flows with Arc-Wise Lower and Upper BoundsInteger Programming and Combinatorial Optimization10.1007/978-3-030-45771-6_23(294-306)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-45771-6_23
Cohen RLewin-Eytan LSeffi Naor JRaz D(2013)Almost optimal virtual machine placement for traffic intense data centers2013 Proceedings IEEE INFOCOM10.1109/INFCOM.2013.6566794(355-359)Online publication date: Apr-2013
https://doi.org/10.1109/INFCOM.2013.6566794
Martens MSalazar FSkutella M(2007)Convex combinations of single source unsplittable flowsProceedings of the 15th annual European conference on Algorithms10.5555/1778580.1778618(395-406)Online publication date: 8-Oct-2007
https://dl.acm.org/doi/10.5555/1778580.1778618
Martens MSalazar FSkutella M(2007)Convex Combinations of Single Source Unsplittable FlowsAlgorithms – ESA 200710.1007/978-3-540-75520-3_36(395-406)Online publication date: 2007
https://doi.org/10.1007/978-3-540-75520-3_36

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents