Toky, cesty a řezy

Petr Kolman

Úterý v 10:40, Malá Strana

Minulé přednášky

13.10.2015
Multikomoditní toky a řezy - úvod, definice problému, ILP formulace + LP relaxace.
20.10.2015
Aproximační algoritmus pro minimální multikomoditní řez. Přibližná dualita, včetně důkazu, že to nejde lépe.
27.10.2015
Nejřidší řez a spravedlivý tok - úvod, LP relaxace řezu.
3.11.2015
Nejřidší řez - aproximační alg. - popis
10.11.2015
Nejřidší řez - aproximační alg. - analýza. Aplikace.
24.11.2015
Aproximace libovolných metrik stromovými.
1.12.2015
Tvrdohlavé routování (oblivious routing).
8.12.2015
Cesty a řezy omezené délky.
15.12.2015
Tokové číslo (definice, smysl, příklady, souvislost s expanzí, zkracovací lemma).
22.12.2015
Hledání max. počtu hranově disjunktních cest. (Ne)souvislost s max. tokem (integrality gap LP relaxace). O(\sqrt{m})- a O(n^{2/3})-aproximace hladovým algoritmem. Aproximace parametrizovaná tokovým číslem. Zobecnění - online, UFP.
5.1.2016
O(log n)-(pseudo)proximace balancovaného nejmenšího řezu pomocí SDP relaxace.
12.1.2016
Dokončení SDP relaxace pro řez.

Anotace

Toky více komodit zobecňují přirozeným způsobem klasický tokový problém: místo jediné dvojice zdroj-spotřebič máme takových dvojic několik, ale přitom máme k dispozici stále jen jedinou siť, do které se musí všechny toky poskládat. Toky více komodit a zejména jejich duální řezové problémy hrály v posledním desetiletí významnou úlohu při návrhu aproximačních algoritmů pro celou radu rozmanitých aplikací, např. pro vyvážené dělení grafu či pro aproximaci expanze grafu. Cílem přednášky je představit vybrané výsledky z této oblasti a ukázat na nich několik obecných postupů užitečných při návrhu aproximačních algoritmů.

Plánovaná témata:

• Přibližná dualita [14]
  • pro součtové toky 
  • pro souběžné toky 
• Toky krátkými cestami [11,3]
• Hledání hranově disjunktních cest a pakovací problémy [10]
• Algoritmy na výpočet toků více komodit
  • Metoda generovaní sloupců [4, kapitola 3.6]
  • Lagrangeova relaxace a hladový algoritmus [6,7]
• Maximální řez a semidefinitní programování [9]
• Nejřidší řez pomocí SDP aproximace [1]

Literatura

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

1. 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.

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

7. 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.

9. 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.

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

11. 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.

14. 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.