Length-Bounded and Dynamic k-Splittable Flows

Maren Martens () and Martin Skutella ()
Additional contact information
Maren Martens: Universität Dortmund
Martin Skutella: Universität Dortmund

A chapter in Operations Research Proceedings 2005, 2006, pp 297-302 from Springer

Abstract: Summary Classical network flow problems do not impose restrictions on the choice of paths on which flow is sent. Only the arc capacities of the network have to be obeyed. This scenario is not always realistic. In fact, there are many problems for which, e.g., the number of paths being used to route a commodity or the length of such paths has to be small. These restrictions are considered in the length-bounded k-splittable s-t-flowproblem: The problem is a variant of the well known classical s-t-flow problem with the additional requirement that the number of paths that may be used to route the flow and the maximum length of those paths are bounded. Our main result is that we can efficiently compute a length-bounded s-t-flow which sends one fourth of the maximum flow value while exceeding the length bound by a factor of at most 2. We also show that this result leads to approximation algorithms for dynamic k-splittable s-t-flows.

Keywords: Approximation Algorithm; Polynomial Time; Average Path Length; Network Flow Problem; Maximum Uniform (search for similar items in EconPapers)
Date: 2006
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-540-32539-0_47

Ordering information: This item can be ordered from
http://www.springer.com/9783540325390

DOI: 10.1007/3-540-32539-5_47

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().