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]

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

Dušan Knop: Parameterized hardness for length-bounded cuts.

Abstract: I would like to present a parametrized result about length bounded cuts, namely that finding an optimal length bounded cut is W[1]-hard when parameterized by path-width only. I will aslo talk a little bit about some lower bound consequences (assuming ETH). I may also sketch some of our algorithmic results. For example an O(n^k) time algorithm where k is the tree-width and O(f(k) n) time algorithm where k is the size of vertex-cover of the input graph.


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

27. 10. 2014 se seminář nekoná

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

Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis of randomized paging algorithms. Theoretical Computer Science 234, 203–218 (2000)
(referuje Lukáš Folwarczny)

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

Dor Arad, Yael Mordechai, Hadas Shachnai: Tighter Bounds for Makespan Minimization on Unrelated Machines. http://arxiv.org/abs/1405.2530.
(referuje Martin Böhm)

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.

Martin Skutella: A note on the ring loading problem. SODA 2015. Also http://arxiv.org/abs/1405.0789.

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ý)

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.

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]