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

Petr Kolman, Jiří Sgall

Doba a místo konání

ÚMLUVA se koná v rámci hromadné úmluvy IÚUK a KAM ve čtvrtek 2. 10. od 14:00, posluchárna S9 

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]


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

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

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

Reuven Bar-Yehuda, Dror Rawitz: On the Equivalence Between the Primal-Dual Schema and the Local Ratio Technique. SIAM J. Discrete Math., 19(3), 762–797.

Thomas Dueholm Hansen, Mike Paterson, and Uri Zwick: Improved upper bounds for Random-Edge and Random-Jump on abstract cubes. SODA 2014.

Stavros G. Kolliopoulos, Yannis Moysoglou: The 2-valued case of makespan minimization with assignment constraints. Inf. Process. Lett. 113(1-2): 39-43 (2013)

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.

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]

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]