NDMI067 Flows, paths and cuts
Winter semester 2017/18
The lecture takes place on Wednesdays, from 12:20 in S11.
Multicommodity flows and cuts - introduction, basic definitions. Approximation algorithm for minimum multicut based on LP relaxation .
Approximation algorithm for minimum multicut - analysis. Approximate duality. Optimality of the result.
Concurrent multicomodity flow and sparsest cut, basic definitions, LP relaxation .
The lecture is canceled.
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 
- for sum multicommodity flow
- for concurrent multicomodity flow
- Flows along short paths [9,3]
- Edge disjoint paths and packing problemsnbsp;
- Algorithms for multicommodity flows
- Column generation [4, kapitola 3.6]
- Lagrange Relaxation and greedy algorithm [5,6]
- Maximum Cut and semidefinite programming 
- The sparsest cut and semidefinite programming 
D. W. Williamson, D. B. Shmoys.
The Design of Approximation Algorithms.
Cambridge University Press, 2011.
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.
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.
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver.
John Wiley, New York, 1997.
L. K. Fleischer.
Approximating fractional multicommodity flow independent of the
number of commodities.
SIAM Journal on Discrete Mathematics, 13(4):505-520, 2000.
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.
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.
Approximation Algorithms for Disjoint Paths Problems.
PhD thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, 1996.
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.
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.