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), 630–652. Jonathan Avron (24/6, 14-17)