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
You can subscribe to the mailing list with the seminar anouncement at

Kontakt, tel. 951 554 155;, tel. 951 554 293.

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

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

Chidambaram Annamalai, Christos Kalaitzis and Ola Svensson: Combinatorial Algorithm for Restricted Max-Min Fair Allocation. SODA 2015. Also
(referuje Štěpán Šimsa)

Abstract: We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4+eps. In contrast, however, the best known approximation algorithm for the problem has an unspecified large constant guarantee.
In this paper we significantly narrow this gap by giving a 13-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [Hax95] for hypergraph matchings, and later used in this context by Asadpour, Feige, and Saberi [AFS12]. For our local search procedure to terminate in polynomial time, we introduce several new ideas such as lazy updates and greedy players. Besides the improved approximation guarantee, the highlight of our approach is that it is purely combinatorial and uses the Configuration-LP only in the analysis. 

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

Haris Aziz, and Simon Mackenzie: A Discrete and Bounded Envy-free Cake Cutting Protocol for Four Agents. STOC 2016, also

Klaus Jansen and Lars Rohwedder: On the Configuration-LP of the Restricted Assignment Problem. SODA 2017, also

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

Magnus Wahlström: LP-branching algorithms based on biased graphs. SODA 2017, also

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

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

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

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]