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]

UMLUVENO: v ZS 2016 se seminář koná v úterý od 10:40 v posluchárně S8.

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]

13. 12. 2016 (úterý [Tuesday], 10:40, MFF UK Malá Strana S8)

Yossi Azar, Amir Epstein, Lukasz Jez, Adi Vardi: Make-to-order integrated scheduling and distribution. SODA 2016. Also http://www.ii.uni.wroc.pl/~mbi/grants/ncn_2014/papers/2016-soda-mto-scheduling.pdf.
(referuje Martin Böhm)

Abstract: Production and distribution are fundamental operational functions in supply chains. The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution to customers afterwards. The goal is to minimize the total time from release to distribution plus total distribution cost to the customers. We design the first poly-logarithmic competitive algorithm for the problem, improving upon previous algorithms with linear competitive ratios. Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines (where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.


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]