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

Petr Kolman, Jiří Sgall

Doba a místo konání

UMLUVENO: seminář se koná v pondělí od 10:40, posluchárna S8, první seminář je 6. 10.

Oznámení o seminářích se distribuuje pomocí mailing listu, do kterého se můžete zapsat na adrese http://list.math.cas.cz/listinfo/algo-seminar.

Kontakt

http://kam.mff.cuni.cz/~kolman/, tel. 221 914 155;
http://iuuk.mff.cuni.cz/~sgall/, tel. 221 914 293.

Nejbližší program semináře [Next program]

15. 12. 2014 (pondělí [Monday], 10:40, MFF UK Malá Strana S8)

Anna R. Karlin, Claire Kenyon, Dana Randall: Dynamic TCP Acknowledgment and Other Stories about e/(e-1). Algorithmica 36(3): 209-224 (2003)
(referuje Lukáš Folwarczný)

Abstract: We present the first optimal randomized online algorithms for the TCP acknowledgment problem [5] and the Bahncard problem [7]. These problems are well-known to be generalizations of the classical online ski rental problem, however, they appeared to be harder. In this paper, we demonstrate that a number of online algorithms which have optimal competitive ratios of e/(e-1), including these, are fundamentally no more complex than ski rental. Our results also suggest a clear paradigm for solving ski rental-like problems.


Předběžný další program [Preliminary future program]

Další články pro ZS 2014 [More papers proposed for this semester]

Andreas Björklund and Thore Husfeldt: Shortest Two Disjoint Paths in Polynomial Time. ICALP 2014 (best paper award).

Yann Disser and Martin Skutella: The Simplex Algorithm is NP-mighty. SODA 2015. Also http://arxiv.org/abs/1311.5935.

Chidambaram Annamalai, Christos Kalaitzis and Ola Svensson: Combinatorial Algorithm for Restricted Max-Min Fair Allocation. SODA 2015. Also http://arxiv.org/abs/1409.0607.

Gábor Braun, Sebastian Pokutta: The matching polytope does not admit fully-polynomial size relaxation schemes. SODA 2015. Also http://arxiv.org/abs/1403.6710.

Alantha Newman: An improved analysis of the Mömke-Svensson algorithm for graph-TSP on subquartic graphs. ESA 2014. Also http://arxiv.org/abs/1407.2524.

Guru Guruganesh, Laura Sanita, Chaitanya Swamy: Region-Growing and Combinatorial Algorithms for k-Route Cut Problems. (k dispozici mailem)

Samozřejmě, jako vždy, jsou vítany jsou i další náměty, zejména pak prezentace vlastních výsledků účastníků semináře.

Další články, o kterých jsme uvažovali, zbylé z minulého semestru atd.
[Additional proposed papers, leftovers from the last semester]

Lorenzo Orecchia, Zeyuan Allen Zhu: Flow-Based Algorithms for Local Graph Clustering. SODA 2014. Also http://arxiv.org/abs/1307.2855.
(referuje Martin Koutecký?)

Marcin Mucha and Maxim Sviridenko: No-Wait Flowshop Scheduling is as Hard as Asymmetric Traveling Salesman Problem. ICALP 2013. Also http://arxiv.org/abs/1302.2551.

Martin Aumuller and Martin Dietzfelbinger:  Optimal Partitioning for Dual Pivot Quicksort. ICALP 2013. Also http://arxiv.org/abs/1303.5217 and slides.

Susanne Albers, Matthias Hellwig: Semi-online scheduling revisited. Theor. Comput. Sci. 443: 1-9 (2012).

Chandra Chekuri, Alina Ene: Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion. SODA 2013.

Hyung-Chan An, Robert Kleinberg, David B. Shmoys: Improving Chrisofides' Algorithm for the s-t Path TSP. STOC 2012.

Subash Khot: On the Unique Games Conjecture. In Proc. 25th Complexity (CCC), 99-121, 2010.

Luca Trevisan: On Khot's unique games conjecture. Bull. Amer. Math. Soc. 49 (2012), 91-111.


Předchozí program semináře [Past program]