Seminář z aproximačních a online algoritmů
Seminar on Approximation and Online Algorithms

Andreas Emil Feldmann, Petr Kolman, Jiří Sgall

Doba a místo konání [Time and place]

ÚMLUVA pro LS 2018 se koná v úterý 20. 2. od 15:40 v S5 v rámci hromadné úmluvy IÚUK a KAM.
Seminář se bude konat v úterý nebo v pátek.

Oznámení o seminářích se distribuuje pomocí mailing listu, do kterého se můžete zapsat na adrese https://kam.mff.cuni.cz/mailman/listinfo/algo-seminar-l.
You can subscribe to the mailing list with the seminar anouncement at https://kam.mff.cuni.cz/mailman/listinfo/algo-seminar-l.

Kontakt

https://sites.google.com/site/aefeldmann/, tel. 951 554 372;
http://kam.mff.cuni.cz/~kolman/, tel. 951 554 155;
http://iuuk.mff.cuni.cz/~sgall/, tel. 951 554 293.

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



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

Martin Skutella: A Note on the Ring Loading Problem. SIAM J. Discrete Math., 30(1), 327-342. 2016.
(presented by Lukáš Folwarczný)

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

Euiwoong Lee: Improved Hardness for Cut, Interdiction, and Firefighter Problems. ICALP 2017. Best Student Paper. Also http://arxiv.org/abs/1607.05133.

Andreas Wiese: A (1+eps)-approximation for Unsplittable Flow on a Path in fixed-parameter running time. ICALP 2017.

Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan: From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS 2017. Also https://arxiv.org/abs/1708.04218.

Michael Lampis: Parameterized Approximation Schemes using Graph Widths. ICALP 2014. Also https://arxiv.org/abs/1311.2466.

Alice Paul, Daniel Freund, Aaron Ferber, David Shmoys and David Williamson: Prize-Collecting TSP with a Budget Constraint. ESA 2017.

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]

Klaus Jansen and Lars Rohwedder: On the Configuration-LP of the Restricted Assignment Problem. SODA 2017: 2670-2678, also https://arxiv.org/abs/1611.01934.

Martijn van Ee, Leo van Iersel, Teun Janssen, René Sitters: A priori TSP in the Scenario Model. WAOA 2016: 183-196.

Alantha Newman, Heiko Röglin, and Johanna Seif: The Alternating Stock Size Problem and the Gasoline Puzzle. ESA 2016. Also https://arxiv.org/abs/1511.09259.

János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin: Online bin packing with cardinality constraints resolved. At https://arxiv.org/abs/1608.06415.

Harald Räcke: Optimal hierarchical decompositions for congestion minimization in networks. STOC 2008:255-264. Also here.

Jittat Fakcheroenphol, Kunal Talwar and Satish Rao: A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003, J. Comput. Syst. Sci. 69(3): 485-497 (2004).


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