Seminář z aproximačních a online algoritmů

Petr Kolman, Jiří Sgall

Doba a místo konání

UMLUVENO: středa 12:20 v S6, první se koná 12. 10.

Oznámení o seminářích se distribuuje pomocí mailing listu, do kterého se můžete zapsat na adrese http://list.math.cas.cz/listinfo/algo-seminar.

Kontakt

http://kam.mff.cuni.cz/~kolman/, tel. 221 914 155;
http://iuuk.mff.cuni.cz/~sgall/, tel. 221 914 293.

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

11. 1. 2012 (středa [Wednesday], 12:20, MFF UK Malá Strana, S6)

Anke van Zuylen: Simpler 3/4-approximation algorithms for MAX SAT. WAOA 2011.
(referuje Lukáš Mach)

Abstract: We consider the recent randomized 3/4-approximation algorithm for MAX SAT of Poloczek and Schnitger. We give a much simpler set of probabilities for setting the variables to true or false, which achieve the same expected performance guarantee. Our algorithm suggests a conceptually simple way to get a deterministic algorithm: rather than comparing to an unknown optimal solution, we instead compare the algorithm's output to the optimal solution of an LP relaxation. This gives rise to a new LP rounding algorithm, which also achieves a performance guarantee of 3/4.

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

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

Thomas Rothvoss: The Entropy Rounding Method in Approximation Algorithms. SODA 2012.

Paul Bonsma and Jens Schulz and Andreas Wiese: A constant factor approximation algorithm for unsplittable flow on paths. FOCS 2011.

Leah Epstein, Csanad Imreh, Asaf Levin and Judit Nagy-Gyorgy: On variants of file caching. ICALP 2011.

Leah Epstein, Asaf Levin: Robust algorithms for preemptive scheduling. WAOA 2011.

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, které zatím nejsou k dispozici [Proposed papers not available online yet]

Anna Adamaszek, Artur Czumaj, Matthias Englert, and Harald Räcke: An O(log k)-competitive Algorithm for Generalized Caching. SODA 2012.

J. Chuzhoy, Y. Makarychev, A. Vijayaraghavan and Y. Zhou: Approximation algorithms and hardness of the k-route cut problem. SODA 2012.

Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, and Roy Schwartz: Min-Max Graph Partitioning and Small-Set Expansion. FOCS 2011.

Zbylé články z minulého semestru

Matthias Poloczek and Georg Schnitger: Randomized Variants of Johnson’s Algorithm for MAX SAT. SODA 2011.

M. Bateni and M. Hajiaghayi: Euclidean Prize-Collecting Steiner Forest. LATIN 2010.

Peng Zhang: An Approximation Algorithm to the k-Steiner Forest Problem. TAMC 2007.

Claire Mathieu and Adrian Vladu: Online Ranking for Tournament Graphs. WAOA 2010.

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