Seminář z aproximačních a online algoritmů

Petr Kolman, Jiří Sgall

Předchozí program semináře, zimní semestr 2008 [Previous program, Fall 2008]

14. 1. 2009 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Jiří Sgall: O algoritmech pro bin-packing s omezeným prostorem

Na posledním semináři uvedu otevřený problém a přehled starších výsledků o algoritmech pro bin-packing s omezeným prostorem, tj. takových, kdy je zaroveň otevřený jen konstantní počet krabic. Ukážu, že Best Fit se dvěma otevřenými krabicemi je 1.7 kompetitivní, a že optimální algoritmus s omezeným prostorem je 1.691 kompetitivní.

17. 12. 2008 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Harald Racke: Optimal Hierarchical Decompositions for Congestion Minimization in Networks.
STOC 2008. Co-Winner of Best Paper Award.
(referuje Petr Kolman)

Abstract: In this paper we show how to construct cut-based decompositions that only result in a logarithmic loss in performance, which is asymptotically optimal. Remarkably, one major ingredient of our proof is a distance-based decomposition scheme due to Fakcharoenphol, Rao and Talwar [16]. This shows an interesting relationship between these seemingly different decomposition techniques. The main applications of the new decomposition are an optimal O(log n)-competitive algorithm for oblivious routing in general undirected graphs, and an O(log n)-approximation for Minimum Bisection, which improves the O(log^1.5 n) approximation by Feige and Krauthgamer [17].

10. 12. 2008 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Leah Epstein, Asaf Levin: Improved Randomized Results for That Interval Selection Problem. ESA 2008.
(referuje Tomáš Ebenlendr)

26. 11. 2008 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Anke van Zuylen: Deterministic Sampling Algorithms for Network Design. ESA 2008 Best student paper.
(referuje Ondřej Zajíček)

Abstract: For several NP-hard network design problems, the best known approximation algorithms are remarkably simple randomized algorithms called Sample-Augment algorithms in [11]. The algorithms draw a random sample from the input, solve a certain subproblem on the random sample, and augment the solution for the subproblem to a solution for the original problem. We give a general framework that allows us to derandomize most Sample-Augment algorithms, i.e. to specify a specific sample for which the cost of the solution created by the Sample-Augment algorithm is at most a constant factor away from optimal. Our approach allows us to give deterministic versions of the Sample-Augment algorithms for the connected facility location problem, in which the open facilities need to be connected by either a tree or a tour, the virtual private network design problem, 2-stage rooted stochastic Steiner tree problem with independent decisions, the a priori traveling salesman problem and the single sink buy-at-bulk problem. This partially answers an open question posed in Gupta et al. [11].

19. 11. 2008 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Jiří Sgall: Něco o nepreemptivním online rozvrhování na počítačích různých rychlostí.

5. 11., 12. 11. 2008 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Rohit Khandekar, Satish Rao, Umesh Vazirani: Graph partitioning using single commodity flows. STOC 2006.
(referuje Petr Kolman)

Abstract: We show that the sparsest cut in graphs can be approximated within O(log^2 n) in \tilde O(n^{3/2)) using polylogarithmic single commodity max-flow computations. Previous algorithms are based on multicommodity flows which take time \tilde O(n^2). Our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. Our technique can also be extended to yield an O(log^2 n) (pseudo) approximation algorithm for the edge-separator problem with a similar runningtime.

22. 10. 2008 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Benjamin Birnbaum and Claire Mathieu: On-line bipartite matching made simple. ACM SIGACT 39:80-87, 2008.
(referuje Tomáš Ebenlendr)

Abstract: We examine the classic on-line bipartite matching problem studied by Karp, Vazirani, and Vazirani [8] and provide a simple proof of their result that the Ranking algorithm for this problem achieves a competitive ratio of 1-1/e.

15. 10. 2008 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Arash Asadpour, Uriel Feige and Amin Saberi. Santa Claus Meets Hypergraph Matchings. To appear in proceedings of Approx 2008.
(referuje Marek Krčál)

8. 10. 2008 (středa [Wednesday], 8:50, MFF UK Malá Strana, posluchárna S8)

Jiří Sgall: Něco o problému frequency assignment
(společná práce s Markem Chrobakem)

Abstrakt: Máme daný graf, v každém vrcholu postupně přicházejí požadavky na přidělení frekvence, případně frekvence mohou být i uvolněny. Frekvence v jednom vrcholu a také na sousedních vrcholech musí být v každém čase různé. Jedná se vlastně o problém barvení speciálních grafů (u izolovaného vrcholu jsou to přesně intervalové grafy). Ukážeme asymptoticky optimální online algoritmus pokud graf je cesta a frekvence se neuvolňují. Dále ukážeme, že problém je NP-těžký. Nakonec zmíníme nějaké otevřené problémy.