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

Petr Kolman, Jiří Sgall

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

ÚMLUVA na LS 2017 se koná v rámci hromadné úmluvy IUUK a KAM v úterý 21.2. od 14:00 v S5

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

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]

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

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.

Haris Aziz, and Simon Mackenzie: A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents. STOC 2016, also http://arxiv.org/abs/1508.05143.

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

Nikhil Bansal, Marek Elias, Lukasz Jez and Grigorios Koumoutsos: The (h,k) server problem on bounded-depth trees. SODA 2017, also https://arxiv.org/abs/1608.08527.

Magnus Wahlström: LP-branching algorithms based on biased graphs. SODA 2017, also https://arxiv.org/abs/1610.06060.

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]

Christos Kalaitzis, Ola Svensson and Jakub Tarnawski: Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios. SODA 2017, also https://arxiv.org/abs/1607.07631.

Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Victor Verdugo, Andreas Wiese: Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines. IPCO 2016.

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.

Guy Even, Moti Medina, and Adi Rosén: A Constant Approximation Algorithm for Scheduling Packets on Line Networks. ESA 2016. Also https://arxiv.org/abs/1602.06174.

Yossi Azar and Oren Gilon: Buffer Management for Packets with Processing Times. ESA 2015.

Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, Andreas Wiese: New Approximation Schemes for Unsplittable Flow on a Path. SODA 2015.

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]