Article

Degree-constrained network flows

Authors:

P. Donovan,

B. Shepherd,

A. Vetta,

G. WilfongAuthors Info & Claims

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

Pages 681 - 688

https://doi.org/10.1145/1250790.1250889

Published: 11 June 2007 Publication History

Get Access

Abstract

A d-furcated flow is a network flow whose support graph has maximum out degree d. Take a single-sink multi-commodity flow problem on any network and with any set of routing demands. Then we show that the existence of feasible fractional flow with node congestion one implies the existence of a d-furcated flow with congestion at most 1+1/(d-1), for d ≥ 2. This result is tight, and sothe congestion gap for d-furcated flows is bounded andexactly equal to 1+ 1/(d-1). For the case d=1 (confluent flows), it is known that the congestion gap is unbounded, namely Θ(log n). Thus, allowing single-sink multicommodity network flows to increase their maximum out degree from one to two virtually eliminates this previously observed congestion gap.

As a corollary we obtain a factor 1 + 1/(d-1)-approximation algorithm for the problem of finding a minimum congestion d-furcated flow; we also prove that this problem is max SNP-hard. Using known techniques these results also extend to degree-constrained unsplittable routing,where each individual demand must be routed along a unique path.

References

[1]

R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.

Digital Library

Google Scholar

[2]

J. Chen, R. Kleinberg, L. Lovasz, R. Rajaraman, R. Sundaram and A. Vetta, "(Almost) tight bounds and existence theorems for confluent flows", Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), pp. 529--538, 2004.

Digital Library

Google Scholar

[3]

J. Chen, R. Rajaraman, and R. Sundaram, "Meet and merge: approximation algorithms for confluent flow", Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), pp. 373--382, 2003.

Digital Library

Google Scholar

[4]

Y. Dinitz, N. Garg and M. Goemans, "On the single-source unsplittable flow problem", Combinatorica, 19, pp. 17--41, 1999.

Crossref

Google Scholar

[5]

J. Kleinberg, "Single-source unsplittable flow", Proceedings of the 37th on Foundations of Computer Science (FOCS), pp. 68--77, 1996.

Digital Library

Google Scholar

[6]

S. Kolliopoulos and C. Stein, "Improved approximation algorithms for unsplittable flow problems", Proceedings of the 38th on Foundations of Computer Science (FOCS), pp. 426--435, 1997.

Digital Library

Google Scholar

[7]

J. Fong, A. C. Gilbert, S. Kannan, and M. Strauss, "Better alternatives to OSPF routing", Algorithmica (Special issue on network design), 43(1-2), pp. 113--131, 2005

Google Scholar

[8]

B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world", IEEE Journal on Selected Areas in Communications (Special Issue on Recent Advances on Fundamentals of Network Management), 20(4), pp. 756--767, 2002.

Digital Library

Google Scholar

[9]

B. Shepherd and A. Vetta, "Visualizing, finding and packing dijoins", in D. Avis, A. Hertz, O. Marcotte (eds.), Graph Theory and Combinatorial Optimization, Kluwer, pp. 219--254, 2005.

Crossref

Google Scholar

Cited By

View all

Perrot NBenhamiche ACarlinet YGourdin E(2021)Future NetworksResearch Anthology on Developing and Optimizing 5G Networks and the Impact on Society10.4018/978-1-7998-7708-0.ch028(677-706)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-7708-0.ch028
Séguin-Charbonneau LShepherd F(2020)Maximum edge-disjoint paths in planar graphs with congestion 2Mathematical Programming10.1007/s10107-020-01513-1Online publication date: 20-May-2020
https://doi.org/10.1007/s10107-020-01513-1
Perrot NBenhamiche ACarlinet YGourdin E(2019)Future NetworksEmerging Automation Techniques for the Future Internet10.4018/978-1-5225-7146-9.ch007(177-207)Online publication date: 2019
https://doi.org/10.4018/978-1-5225-7146-9.ch007
Show More Cited By

Index Terms

Degree-constrained network flows
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

Augmenting anycast network flows
ICDCN '16: Proceedings of the 17th International Conference on Distributed Computing and Networking

Updating network flows in a real-world setting is a nascent research area, especially with the recent rise of Software Defined Networks. While augmenting s-t flows of a single commodity is a well-understood concept, we study updating flows in a multi-...
(Almost) Tight bounds and existence theorems for single-commodity confluent flows

A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single destination ...
Flows on few paths: Algorithms and lower bounds

The classical network flow theory allows decomposition of flow into several chunks of arbitrary sizes traveling through the network on different paths. In the first part of this article we consider the unsplittable flow problem where all flow traveling ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

June 2007

734 pages

ISBN:9781595936318

DOI:10.1145/1250790

General Chair:
David Johnson
AT&T Labs - Research
,
Program Chair:
Uriel Feige
Microsoft Research and Weizmann Institute

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: 11 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC07

Sponsor:

STOC07: Symposium on Theory of Computing

June 11 - 13, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
425
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)3

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Perrot NBenhamiche ACarlinet YGourdin E(2021)Future NetworksResearch Anthology on Developing and Optimizing 5G Networks and the Impact on Society10.4018/978-1-7998-7708-0.ch028(677-706)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-7708-0.ch028
Séguin-Charbonneau LShepherd F(2020)Maximum edge-disjoint paths in planar graphs with congestion 2Mathematical Programming10.1007/s10107-020-01513-1Online publication date: 20-May-2020
https://doi.org/10.1007/s10107-020-01513-1
Perrot NBenhamiche ACarlinet YGourdin E(2019)Future NetworksEmerging Automation Techniques for the Future Internet10.4018/978-1-5225-7146-9.ch007(177-207)Online publication date: 2019
https://doi.org/10.4018/978-1-5225-7146-9.ch007
Yallouz JBlocq GRevah YKadosh AOrda A(2015)"Don't Let the Stack Get Stuck": A Novel Approach for Designing Efficient Stackable Routers2015 IEEE 16th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2015.7483081(1-8)Online publication date: Jul-2015
https://doi.org/10.1109/HPSR.2015.7483081
Shepherd FVetta AWilfong G(2015)Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow ProblemProceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2015.51(748-758)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1109/FOCS.2015.51
Cohen RLewin-Eytan LNaor JRaz D(2014)On the effect of forwarding table size on SDN network utilizationIEEE INFOCOM 2014 - IEEE Conference on Computer Communications10.1109/INFOCOM.2014.6848111(1734-1742)Online publication date: Apr-2014
https://doi.org/10.1109/INFOCOM.2014.6848111
Hadynski GLee SRajappan GSundaram RWang XZhou F(2010)Optimization of directional antenna network topology in Airborne Networks2010 - MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE10.1109/MILCOM.2010.5680269(68-73)Online publication date: Oct-2010
https://doi.org/10.1109/MILCOM.2010.5680269
Shepherd F(2009)Single-Sink Multicommodity Flow with Side ConstraintsResearch Trends in Combinatorial Optimization10.1007/978-3-540-76796-1_20(429-450)Online publication date: 2009
https://doi.org/10.1007/978-3-540-76796-1_20

View Options

Login options

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

Cited By

Index Terms

Recommendations

Augmenting anycast network flows

(Almost) Tight bounds and existence theorems for single-commodity confluent flows

Flows on few paths: Algorithms and lower bounds