Seminar on Network Flow Algorithms, spring 12/13

Haim Kaplan

We will follow some chapters of the book on Network Flows by Ahuja, Magnanti, and Orlin (Prentice-Hall 1993) and a few more recent papers. The chapters are from the second half of the book and you may need occasionally to look also at the first few chapters. Some topics are too large for a single slot so two students would split it between them. Below is a list of tentative topics and in parenthesis I indicate whether it should fit into one or two slots.

Announcements

  We will not have classes on April 22 and June 10.

  We will have additional two makeup classes at:

1) Friday May 3, 10-12
2) Monday June 24 14-17, this is 2 days after the semester ends in our
regular time slot, but I would like to end at 17 rather than 16, you should
not have a conflict since classes end on June 21.

 

Tentative schedule

1. An overview of maximum flow algorithms

2. Chapter 9: Minimum cost flows: Introduction and basic algorithms, Benjamin Klein (11/3), Adi Haviv (18/3)

3. Chapter 10: Minimum cost flow: Polynomial algorithms, Ronnie Barequet (8/4), Omri Ben Eliezer (Thursday 11/4 at 18:00)

4. Chapter 11: Minimum cost flows: network simplex algorithms, Lior Teller (29/4) and the paper "A polynomial time primal network simplex algorithm for minimum cost flows", J. Orlin, Mathematical Programming 78, 1997, Tal Kaminker (Friday 3/5 at 10)

5. "A faster strongly polynomial algorithm for minimum cost flow", J. Orlin, Operations Research 41 (2), 1993, Aviv Eisenschtat (6/5)

6. Chapter 12: Assignments and matchings, Yorai Geffen (13/5)

7. The auction algorithm, Chapter 7 in the book by D. P. Bertsekas: Network Optimization, continuous and discrete models, Shahar (20/5)

8. Chapter 15. Generalized flows, Jonathan Kalechstain (27/5)

 

9. "A polynomial combinatorial algorithm for generalized minimum cost flow", K. Wayne, Math. of Operations Research 27(3), 2002, Eyal Dushkin (3/6)

 

10. Chapter 16: Lagrangian relaxation and network optimization, Alexey Pechorin (17/6)

11. Chapter 17: Multicommodity flows, Idan Maor (24/6, 14-17, possibly start at 17/6)

12. Garg and Konemann, Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems, SIAM J. Comput., 37(2), 630652. Jonathan Avron (24/6, 14-17)