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 LS 2017 se seminář koná v pondělí od 12:20 v S4

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]

20. 3. 2017 (pondělí [Monday], 12:20, MFF UK Malá Strana S4)

Rebecca Hoberg and Thomas Rothvoss: A Logarithmic Additive Integrality Gap for Bin Packing. SODA 2017: 2616-2625.
(referuje Pavel Veselý)

Abstract: For bin packing, the input consists of n items with sizes s1,…, sn in [0,1] which have to be assigned to a minimum number of bins of size 1. Recently, the second author gave an LP-based polynomial time algorithm that employed techniques from discrepancy theory to find a solution using at most OPT + O(logOPT * loglog OPT) bins. In this paper, we build on the techniques of Rothvoss to present an approximation algorithm that has an additive gap of only O(log OPT) bins. This gap matches certain combinatorial lower bounds, and any further improvement would have to use more algebraic structure.


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

Další články pro ZS 2015 [More papers proposed for this 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.

Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, Hang Zhou: To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. SODA 2017: 2411-2422.
(referuje Štěpán Šimsa)

Martin Skutella: A Note on the Ring Loading Problem. SIAM J. Discrete Math. 30: 327-342 (2016). Also https://arxiv.org/abs/1405.0789.

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

Esther M. Arkin, Jie Gao, Adam Hesterberg, Joseph S. B. Mitchell, Jiemin Zeng: The Shortest Separating Cycle Problem. WAOA 2016: 1-13.

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]

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.

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.

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]