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

Petr Kolman, Jiří Sgall

Doba a místo konání

UMLUVENO: v LS 2015 se koná v pondělí od 10:40 v S8

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]

23. 2. 2015 (Pondělí [Monday], MFF UK Malá Strana S8)

Lukáš Folwarczný: Caching Is Hard: Even For Small Pages

Abstract: General caching (pages have arbitrary sizes and fault costs) in the offline setting has been studied since 1990s. In 2010, it was shown that general caching is strongly NP-hard, even when all pages have fault cost one (this case is known as the fault model). However, pages of arbitrary size (e.g. as big as half of the cache) are needed to prove that the problem is hard. In real-life problems, pages are likely to be small in comparison with the size of the cache. We present a new reduction that proves the strong NP-hardness of caching in the fault model with page sizes restricted to {1, 2, 3}.


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.

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

Nikhil Bansal: Approximating independent sets in sparse graphs. SODA 2015.

Deeparnab Chakrabarty, Sanjeev Khanna and Shi Li: On Restricted Assignment Makespan Minimization. SODA 2015. Also http://arxiv.org/abs/1410.7506.Anupam Gupta and Amit Kumar: Greedy Algorithms for Steiner Forest. STOC 2015. Also http://arxiv.org/abs/1412.7693.

Gábor Braun, Sebastian Pokutta, Daniel Zink: Inapproximability of combinatorial problems via small LPs and SDPs. STOC 2015.

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]