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

Petr Kolman, Jiří Sgall

ZMĚNA ADRESY

Nová adresa webové stránky semináře je

http://kam.mff.cuni.cz/~sgall/algo/
Zde zůstává pouze

Archiv do r. 2008

Doba a místo konání

Doba konání se rozhoduje na hromadné úmluvě KAM vždy v prvním týdnu semestru. Seminář se koná na MFF Mala Strana.

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

sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 222 090 780;
http://kam.mff.cuni.cz/~kolman/, tel. 221 914 233.

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

Předběžný připravovaný program semináře [Preliminary future program]

René A. Sitters: Approximability of Average Completion Time Scheduling on Unrelated Machines. ESA 2008.
(referuje Marek Krčál)

Sanjeev Arora, James Lee, and Assaf Naor: Euclidean distortion and the sparsest cut. STOC 2005.
(referuje Jakub Bystroň)

Abstract: We prove that every n-point metric space of negative type (in particular, every n-point subset of L1) embeds into a
Euclidean space with distortion O(sqrt(log n) log log n), a result which is tight up to the O(log log n) factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size k, we achieve an approximation ratio of O(sqrt(log k) log log k).

Další články pro ZS 2008

Sanjeev Arora, Elad Hazan, and Satyen Kale: Multiplicative weights method: a meta-algorithm and its applications.

Moses Charikar, Mohammad Taghi Hajiaghayi, Howard Karloff, Satish Rao: l_2^2 spreading metrics for vertex ordering problems. SODA 2006.

J.Konemann., S. Leonardi, G. Schäfer: A Group-Strategyproof Mechanism for Steiner Forests. SODA 2005.

S. Khanna, T. Chakraborty and J. Chuzhoy: Network Design for Vertex Connectivity. STOC 2008.

C. Chekuri and S. Khanna. and F. Bruce Shepherd: A Note on Multiflows and Treewidth. Algorithmica, Nov. 2007.

Zoltán Király: Better and Simpler Approximation Algorithms for the Stable Marriage Problem. ESA 2008 Best paper award.

Stanley P. Y. Fung, Chung Keung Poon, Feifeng Zheng: Improved Randomized Online Scheduling of Unit Length Intervals and Jobs. WAOA 2008.

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.

Zbylé články z minulých semestrů

Tady je seznam neprobraných článků, o kterých jsme také uvažovali. Nejspíš se na ně už nedostane, ale když už jsem ty odkazy našel, tak tu ještě chvíli mohou být.

Amit Agarwal, Noga Alon, Moses S. Charikar: Improved approximation for directed cut problems, STOC 2007

Ch. Chekuri, Guy Even, Anupam Gupta, and Danny Segev: Set Connectivity Problems in Undirected Graphs and the Directed Steiner Network Problem. SODA 2008.

Christos Koufogiannakis, Neal Young: Beating Simplex for Fractional Packing and Covering Linear Programs. FOCS 2007

Sanjeev Arora, Satyen Kale. A combinatorial, primal-dual approach to solving SDPs. STOC 2007.

I. Caragiannis: Better bounds for online load balancing on unrelated machines. SODA 08.

Julien Robert and Nicolas Schabanel: Non-Clairvoyant Scheduling with Precedence Constraints. SODA 08.

Yossi Azar and Kamal Jain and Vahab Mirrokni: (Almost) Optimal Coordination Mechanisms for Unrelated Machine Scheduling. SODA 08.

Fei Li, Jay Sethuraman, and Clifford Stein: Better Online Buffer Management. SODA'07.

Matthias Englert and Matthias Westermann: Considering Suppressed Packets Improves Buffer Management in QoS Switches. SODA'07.

Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar: Approximation Algorithms via Contraction Decomposition. SODA'07.

Kontakt

sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 222 090 780;
http://kam.mff.cuni.cz/~kolman/, tel. 221 914 233.

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