## Network Flows

### (ADM III), WS 09/10

LV-Nr.: 3236 L 246

### Prospective Schedule

Lectures (including exercise sessions):

- Lecture, Tuesday, 10:15 to 11:45 in MA 651.
- Lecture, Wednesday, 10:15 to 11:45 in MA 651.

### Contents

Network flows are among the most important problems studied in Combinatorial Optimization. Beyond the basic problems such as the Max Flow Problem and the Min Cost Flow Problem treated in introductory courses on Combinatorial Optimization (ADM I), there are numerous other variants of network flows that are interesting both from a theoretical and a practical point of view. In this course we give an overview of the entire area of network flows and treat some selected advanced network flow problems in more detail. Here are some examples:

- Multicommodity Flows
- Edge Disjoint Paths
- Unsplittable Flows
*k*-Splittable Flows- Generalized Flows
- Length-Bounded Flows
- Flows Over Time

### Requirements

In addition to the usual mathematical basics, good knowledge of linear and combinatorial optimization is required.

### Content of lectures and suggested reading

In the following we give a short list of topics covered in each lecture together with pointers to the literature:

**Oct. 14:**recapitulation: maximum flows, MaxFlow-MinCut Theorem, LP formulations in arc and path variables, column generation and solving the pricing problem in the path formulation via shortest path computation**Suggested reading:**basic chapter on network flows in any textbook; Section 70.13d in Schrijver's book**Oct. 20:**origins of MaxFlow-MinCut, Fujishige's algorithm for maximum flows; recapitulation: minimum cost flows, negative cycle criterion, node potentials**Suggested reading:**Sect. 10.8e in Schrijver's book; Sect. 8.4 in Korte & Vygen's book; min-cost flows in any textbook**Oct. 21:**discussion of first set of exercises; introduction to multicommodity flows and edge-disjoint paths; distance criterion; cut criterion**Suggested reading:**Sect. 19.1 in Korte & Vygen's book**Oct. 27:**an FPTAS for maximum multicommodity flows**Suggested reading:**Sect. 19.2 in Korte & Vygen's book**Oct. 28:**discussion of second set of exercises; directed arc-disjoint paths problem**Suggested reading:**Sect. 19.3 in Korte & Vygen's book (up to Theorem 19.9); parts of Chapt. 70 in Schrijver's book**Nov. 3:**undirected edge-disjoint paths problem**Suggested reading:**Sect. 19.4 in Korte & Vygen's book (up to Theorem 19.17); parts of Chapt. 70 in Schrijver's book**Nov. 4:**Rothschild-Whinston Theorem and 2-commodity flows in undirected graphs**Suggested reading:**rest of Sect. 19.4 in Korte & Vygen's book; Sect. 71.1 in Schrijver's book**Nov. 10:**unsplittable flows and randomized rounding**Suggested reading:**Sect. 4.1 in Motwani & Raghavan's book; Raghavan's PhD thesis**Nov. 11:**discussion of third set of exercises; single-source unsplittable flows**Suggested reading:**papers of Dinitz, Garg & Goemans (up to Sect. 3) and Skutella (Sect. 2);**Nov. 17:**single-source unsplittable flows;*k*-splittable flows**Suggested reading:**papers of Dinitz, Garg & Goemans (Sect. 4) and Baier, Köhler & Skutella (Sect. 2.1 and Sect. 4);-
**Suggested reading:**paper of Baier, Köhler & Skutella (Sect. 2.2); **Nov. 24:***k*-splittable flows; generalized flows**Suggested reading:**paper of Baier, Köhler & Skutella (Sect. 2.2 & 2.3); lecture 26 in lecture notes of David Williamson; more details can be found in the PhD thesis of Kevin D. Wayne**Nov. 25:**discussion of fifth set of exercises; generalized flows**Suggested reading:**lecture 26 in lecture notes of David Williamson; more details can be found in the PhD thesis of Kevin D. Wayne**Dec. 1:**generalized flows**Suggested reading:**lecture 27 in lecture notes of David Williamson; more details can be found in the PhD thesis of Kevin D. Wayne**Dec. 2:**generalized flows**Suggested reading:**lecture 28 in lecture notes of David Williamson; more details can be found in the PhD thesis of Kevin D. Wayne**Dec. 8:**length-bounded shortest paths**Suggested reading:**Section 1.3 in the PhD thesis of Georg Baier and references therein.**Dec. 9:**discussion of sixth set of exercises; length-bounded flows**Suggested reading:**Chapter 2 in the PhD thesis of Georg Baier**Dec. 15:**length-bounded flows**Suggested reading:**Chapter 2 in the PhD thesis of Georg Baier**Dec. 16:**length-bounded flows**Suggested reading:**Chapter 2 in the PhD thesis of Georg Baier**Jan. 5:**flows over time**Suggested reading:**Sections 1 and 2 in An Introduction to Network Flows Over Time**Jan. 6:**discussion of seventh set of exercises; maximum flows over time**Suggested reading:**Section 2 in An Introduction to Network Flows Over Time**Jan. 12:**maximum flows over time**Suggested reading:**Section 2 in An Introduction to Network Flows Over Time**Jan. 13:**discussion of eighth set of exercises; earliest arrival flows**Suggested reading:**Section 3 in An Introduction to Network Flows Over Time**Jan. 19:**discussion of ninth set of exercises; earliest arrival flows and Nash flows over time**Suggested reading:**Section 3 in An Introduction to Network Flows Over Time**Jan. 26:**Nash flows over time and min-cost flows over time**Suggested reading:**Section 4 in An Introduction to Network Flows Over Time**Jan. 27:**multi-commodity flows over time**Suggested reading:**Section 5 in An Introduction to Network Flows Over Time**Feb. 9:**a local-control approximation algorithm for multicommodity flow**Suggested reading:**lecture 36 in lecture notes of David Williamson; more details can be found in the paper of Awerbuch and Leighton**Feb. 10:**discussion of tenth set of exercises; a local-control approximation algorithm for multicommodity flow (cont.)**Suggested reading:**lecture 37 in lecture notes of David Williamson; more details can be found in the paper of Awerbuch and Leighton

### Exercises

- First Set of Exercises (due date: Oct. 21, 2009)
- Second Set of Exercises (due date: Oct. 28, 2009)
- Third Set of Exercises (due date: Nov. 11, 2009)
- Fourth Set of Exercises (due date: Nov. 18, 2009)
- Fifth Set of Exercises (due date: Nov. 25, 2009)
- Sixth Set of Exercises (due date: Dec. 9, 2009)
- Seventh Set of Exercises (due date: Jan. 6, 2010)
- Eighth Set of Exercises (due date: Jan. 13, 2010)
- Ninth Set of Exercises (due date: Jan. 19, 2010)
- Tenth Set of Exercises (due date: Feb. 3, 2010)

### Contact

- Lecturer: Prof. Dr. Martin Skutella, MA 521, phone: 030 314-78654, e-mail: martin.skutella'at'tu-berlin.de, office hours: by appointment.
- Secretary: Dorothea Kiefer, MA 501, phone: 030 314-28641, e-mail: kiefer'at'math.tu-berlin.de, office hours: Mon, Tue, Thu and Fry 9:30 - 11:30.

### Literature

We recommend to have a look at some of the books in the following list once in a while:

- R. Ahuja, T. Magnanti, J. Orlin. "Network flows, Theory, Algorithms, and Applications". Prentice Hall 1993.
- B. Awerbuch, T. Leighton. "A simple local-control approximation algorithm for multicommodity flow". In Proceedings of the 3rd IEEE Symposium on Foundations of Computer Science, pages 459-46. IEEE, November 1993.
- B. Awerbuch, T. Leighton. "Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks". Proceedings of the 26th annual ACM Symposium on Theory of Computing, pages 487-496, 1994.
- G. Baier. Flows with Path Restrictions, PhD thesis, TU Berlin, 2003.
- G. Baier, E. Köhler, M. Skutella. "The
*k*-splittable flow problem". Algorithmica 42(3-4), 231-248, 2005. - W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver."Combinatorial Optimization". John Wiley & Sons, Inc, 1998.
- Y. Dinitz, N. Garg, M. X. Goemans. "On the Single-Source Unsplittable Flow Problem". Combinatorica 19(1), 17-41, 1999.
- L. R. Ford, D. R. Fulkerson. "Flows in networks". Princeton University Press 1962.
- B. Korte and J. Vygen. "Combinatorial Optimization, Theory and Algorithms". Springer Verlag 2001.
- R. Motwani, P. Raghavan. "Randomized Algorithms". Cambridge University Press 1995.
- C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, reprint 1998.
- P. Raghavan. "Randomized Rounding And Discrete Ham-Sandwich Theorems: Provably Good Algorithms for Routing and Packing Problems". PhD thesis, University of California, Berkeley 1986.
- A. Schrijver. "Combinatorial Optimization - Polyhedra and Efficiency". Springer Verlag 2003.
- M. Skutella. Approximating the single source unsplittable min-cost flow problem. Mathematical Programming, 91(3), 493-514, 2002.
- M. Skutella. An Introduction to Network Flows Over Time, in W. Cook, L. Lovász and J. Vygen (eds.): Research Trends in Combinatorial Optimization. Springer: Berlin 2009, pp. 451-482.
- K. D. Wayne. "Generalized Maximum Flow Algorithms". PhD thesis, Cornell University, 1999.

Most of the books are available in the Mathematical Library.