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

Petr Kolman, Jiří Sgall

Předchozí program semináře, letní semestr 2010 [Previous program, Spring 2010]

18. 5. 2010 (úterý [Tuesday], 9:00, MFF UK Malá Strana, S9)

Marek Chrobak, Gerhard J. Woeginger, Kazuhisa Makino, and Haifeng Xu: Caching is Hard - Even in the Fault Model. ESA 2010.
(referuje Peter Šufliarsky)

Abstract: We prove strong NP-completeness for the four variants of caching with multi-size pages. These four variants are obtained by choosing either the fault cost or the bit cost model, and by combining it with either a forced or an optional caching policy. This resolves two complexity questions in the area of paging and caching that were open since the 1990s.

4. 5., 11. 5. 2010 (úterý [Tuesday], 9:00, MFF UK Malá Strana, S9)

Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi:
An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. SODA 2010.
(referuje Vítězslav Zajíc)

Abstract: We consider the Asymmetric Traveling Salesman problem for costs satisfying the triangle inequality. We derive a randomized algorithm which delivers a solution within a factor O(log n/ log log n) of the optimum with high probability.

20. 4., 27. 4. 2010 (úterý [Tuesday], 9:00, MFF UK Malá Strana, S9)

Ron Aharoni, Eli Berger: The intersection of a matroid and a simplicial complex. Trans. AMS 358 (2006), 4895-4917.
(referuje Marek Krčál)

Abstract: A classical theorem of Edmonds provides a min-max formula relating the maximal size of a set in the intersection of two matroids to a "covering" parameter. We generalize this theorem, replacing one of the matroids by a general simplicial complex. One application is a solution of the caser=3 of a matroidal version of Ryser's conjecture. Another is an upper bound on the minimal number of sets belonging to the intersection of two matroids, needed to cover their common ground set. This, in turn, is used to derive a weakened version of a conjecture of Rota. Bounds are also found on the dual parameter--the maximal number of disjoint sets, all spanning in each of two given matroids. We study in detail the case in which the complex is the complex of independent sets of a graph, and prove generalizations of known results on ``independent systems of representatives" (which are the special case in which the matroid is a partition matroid). In particular, we define a notion of k-matroidal colorability of a graph, and prove a fractional version of a conjecture, that every graph G is 2-Delta(G) matroidally colorable.

6. 4., 13. 4. 2010 (úterý [Tuesday], 9:00, MFF UK Malá Strana, S9)

Chandra Chekuri, Alina Ene, Nitish Korula: Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. APPROX-RANDOM 2009.
(referuje Dušan Knop)

Abstract: We consider the unsplittable flow problem (UFP) and the closely related column-restricted packing integer programs (CPIPs). In UFP we are given an edge-capacitated graph G = (V,E) and k request pairs R_1, . . . , R_k, where each R_i consists of a source-destination pair (s_i, t_i), a demand d_i and a weight w_i. The goal is to find a maximum weight subset of requests that can be routed unsplittably in G. Most previous work on UFP has focused on the no-bottleneck case in which the maximum demand of the requests is at most the smallest edge capacity. Inspired by the recent work of Bansal et al. [3] on UFP on a path without the above assumption, we consider UFP on paths as well as trees. We give a simple O(log n) approximation for UFP on trees when all weights are identical; this yields an O(log^2 n) approximation for the weighted case. These are the first non-trivial approximations for UFP on trees. We develop an LP relaxation for UFP on paths that has an integrality gap of O(log^2 n); previously there was no relaxation with o(n) gap. We also consider UFP in general graphs and CPIPs without the no-bottleneck assumption and obtain new and useful results.

16. 3., 23. 3. 2010 (úterý [Tuesday], 9:00, MFF UK Malá Strana, S9)

Siddharth Barman and Shuchi Chawla: Region Growing for Multi-Route Cuts. SODA 2010.
(referuje Petr Kolman)

Abstract: We study a number of multi-route cut problems: given a graph G = (V,E) and connectivity thresholds k(u,v) on pairs of nodes, the goal is to find a minimum cost set of edges or vertices the removal of which reduces the connectivity between every pair (u, v) to strictly below its given threshold. We provide the first non-trivial approximations to a number of variants of the problem including for both node-disjoint and edge-disjoint connectivity thresholds. A main contribution of our work is an extension of the region growing technique for approximating minimum multicuts to the multi-route setting. When the connectivity thresholds are either 2 or 1 (the “2-route cut” case), we obtain polylogarithmic approximations while satisfying the thresholds exactly. For arbitrary connectivity thresholds this approach leads to bicriteria approximations where we approximately satisfy the thresholds and approximately minimize the cost. We present a number of different algorithmsachieving different cost-connectivity tradeoffs.

9. 3. 2010 (úterý [Tuesday], 9:00, MFF UK Malá Strana, S9)

René Sitters: Efficient algorithms for average completion time scheduling.
(referuje Ondřej Zajíček)

Abstract: We analyze the competitive ratio of algorithms for minimizing (weighted) average completion time on identical parallel machines and prove that the well-known shortest remaining processing time algorithm (SRPT) is 5/4-competitive w.r.t. the average completion time objective. For weighted completion times we give a deterministic algorithm with competitive ratio 1.791+o(m). This ratio holds for preemptive andnon-preemptive scheduling.

2. 3. 2010 (úterý [Tuesday], 9:00, MFF UK Malá Strana, S9)

J. Sgall: O problému přidělování frekvencí pro bipartitní grafy

Abstrakt: V tomto problému je dán graf. Postupně přicházejí požadavky asociované s jednotlivými vrcholy (i více u jednoho vrcholu). Je třeba je obarvit tak, aby požadavky na daném vrcholu i na jeho sousedech měly různé barvy.

Na úvodním semináři povím něco o výsledcích, které jsme získali během prosincové návštěvy Lukasze Jeze. Jde o nový algoritmus a nový dolní odhad, oboje pro bipartitní grafy, a oboje zlepšuje dosavadní známé odhady pro asymptotický kompetitivní poměr.