NDMI067 Flows, paths and cuts

Winter semester 2017/18

Petr Kolman

The lecture takes place on Wednesdays, from 12:20 in S11.

Covered topics

• 4.10.2017
  Multicommodity flows and cuts - introduction, basic definitions. Approximation algorithm for minimum multicut based on LP relaxation [10].
• 11.10.2017
  Approximation algorithm for minimum multicut - analysis. Approximate duality. Optimality of the result.
  Concurrent multicomodity flow and sparsest cut, basic definitions, LP relaxation [10].
• 18.10.2017
  The lecture is canceled.
• 25.10.2017
  Approximation algorithm for sparsest cut problem based on rounding the LP relaxation - Part I.
• 1.11.2017
  Approximation algorithm for sparsest cut problem based on rounding the LP relaxation - Part II.
• 8.11.2017
  No lecture - Dean's Day
• 15.11.2017
  Approximation algorithm for sparsest cut problem based on rounding the LP relaxation - Part III. Connections to embeddings of metric spaces.
• 22.11.2017
  Applications of the approximation algorithm for sparsest cut problem: pseudoapproximation for balanced cut, minimum cut linear arrangement.
  L-bounded cuts and flows - introduction, LP formulations.
• 29.11.2017
  L-bounded cut problem. Integrality gap of a natural LP relaxation. Approximation algorithms.
• 5.12.2017
  Flow number of a graph. Balanced multicommodity flow.
• 12.12.2017
  Flow shortening lemma. Edge disjoint path problem. Greedy algorithm.
• 19.12.2017
  Max Cut and Semidefinite Programming.
• 3.1.2018
  Minimum balanced cut and Semidefinite Programming.
• 10.1.2018
  Analysis of an SDP approximation algorithm for Minimum balanced cut.
  Column generation.

Sylabus

Multicommodity flows generalize in a natural way the classical flow problem: instead of just a single source-destination pair, there are several such pairs but there is still just one network and all flows must fit in it. Multicommodity flows and their dual cut problems are extremely useful in the design of approximation algorithms for many different graph problems. The lecture will provide an overview of the most important result in this area.

• Approximate duality [10]
  • for sum multicommodity flow 
  • for concurrent multicomodity flow 
• Flows along short paths [9,3]
• Edge disjoint paths and packing problems [8]
• Algorithms for multicommodity flows
  • Column generation [4, kapitola 3.6]
  • Lagrange Relaxation and greedy algorithm [5,6]
• Maximum Cut and semidefinite programming [7]
• The sparsest cut and semidefinite programming [2]

Textbooks, relevant papers

1. D. W. Williamson, D. B. Shmoys.
The Design of Approximation Algorithms.
Cambridge University Press, 2011.

2. S. Arora, S. Rao, and U. Vazirani.
Expander flows, geometric embeddings, and graph partitionings.
Journal of the AMC, 56(2):5.1-5.37, 2009.

3. Baier, G., Erlebach, T., Hall, A., Köhler, E., Kolman P., Pangrác O., Schilling, H., and Skutella, M.
Length-bounded cuts and flows.
ACM Transactions on Algorithms, Volume 7, Issue 1, Article No. 4, 2010.

4. W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver.
Combinatorial Optimization.
John Wiley, New York, 1997.

5. L. K. Fleischer.
Approximating fractional multicommodity flow independent of the number of commodities.
SIAM Journal on Discrete Mathematics, 13(4):505-520, 2000.

6. N. Garg and J. Konemann.
Faster and simpler algorithms for multicommodity flow and other fractional packing problems.
In Proc. of the 39th Annual Symposium on Foundations of Computer Science, 300-309, 1998.

7. M. X. Goemans and D. P. Williamson.
.878-approximation algorithms for MAX CUT and MAX 2SAT.
In Proc. of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, 422-431, 1994.

8. J. Kleinberg.
Approximation Algorithms for Disjoint Paths Problems.
PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1996.

9. P. Kolman and C. Scheideler.
Improved bounds for the unsplittable flow problem.
In Proc. of the 13th ACM-SIAM Symposium on Discrete Algorithms, 184-193, 2002.

10. D. B. Shmoys.
Cut problems and their application to divide-and-conquer.
In D. S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, 192-235. PWS Publishing Company, 1997.