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

Petr Kolman, Jiří Sgall

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

17. 5., 24. 5. 2011 (úterý [Tuesday], 8:30, MFF UK Malá Strana, S6)

Dániel Marx and Igor Razgon: Fixed-parameter tractability of multicut parameterized by the size of the cutset. STOC 2011.
(referuje Dušan Knop)

Abstract: Given an undirected graph $G$, a collection $\{(s_1,t_1),..., (s_k,t_k)\}$ of pairs of vertices, and an integer $p$, the Edge Multicut problem ask if there is a set $S$ of at most $p$ edges such that the removal of $S$ disconnects every $s_i$ from the corresponding $t_i$. Vertex Multicut is the analogous problem where $S$ is a set of at most $p$ vertices. Our main result is that both problems can be solved in time $2^{O(p^3)}... n^{O(1)}$, i.e., fixed-parameter tractable parameterized by the size $p$ of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form $f(p)... n^{O(1)}$ exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

3. 5., 10. 5. 2011 (úterý [Tuesday], 8:30, MFF UK Malá Strana, S6)

Friedrich Eisenbrand, Dömötör Pálvölgyi, and Thomas Rothvoss:
Bin Packing via Discrepancy of Permutations. SODA 2011.
(referuje Tomáš Dzetkulič)

Abstract: A well studied special case of bin packing is the 3-partition problem, where n items of size >1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins.
The three-permutations-conjecture of Beck is the following. Given any 3 permutations on n symbols, one can color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols differs only by a constant. Beck's conjecture is well known in the field of discrepancy theory.
We establish a surprising connection between bin packing and Beck's conjecture: If the latter holds true, then the additive integrality gap of the 3-partition linear programming relaxation is bounded by a constant.

19. 4., 26. 4. 2011 (úterý [Tuesday], 8:30, MFF UK Malá Strana, S6)

Ola Svensson: Santa Claus Schedules Jobs on Unrelated Machines. STOC 2010.
(referuje Marek Krčál)

Abstract: One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines, i.e., job j requires time p_{ij} if processed on machine i. More than two decades after its introduction it is still the algorithm of choice even in the restricted model where processing times are of the form p_{ij} in {p_j, \infty}. This problem, also known as the restricted assignment problem, is NP-hard to approximate within a factor less than 1.5 which is also the best known lower bound for the general version. Our main result is a polynomial time algorithm that estimates the optimal makespan of the restricted assignment problem within a factor 33/17 + \epsilon \approx 1.9412 + \epsilon, where \epsilon > 0 is an arbitrary small constant. The result is obtained by upper bounding the integrality gap of a certain strong linear program, known as configuration LP, that was previously successfully used for the related Santa Claus problem. Similar to the strongest analysis for that problem our proof is based on a local search algorithm that will eventually find a schedule of the mentioned approximation guarantee, but is not known to converge in polynomial time.

12. 4. 2011 (úterý [Tuesday], 8:30, MFF UK Malá Strana, S6)

Robin A. Moser and Dominik Scheder: A Full Derandomization of Schoening's k-SAT Algorithm. STOC 2011.
(referuje Vojtěch Bardejovský)

Abstract: Schoening [7] presents a simple randomized algorithm for k-SAT with running time O(a_k^n poly(n)) for a_k = 2(k − 1)/k. We give a deterministic version of this algorithm running in time O((a_k + eps)n poly(n)), where eps>0 can be made arbitrarily small.

29. 3., 5. 4. 2011 (úterý [Tuesday], 8:30, MFF UK Malá Strana, S6)

Georg Gottlob, Reinhard Pichler, Fang Wei: Monadic datalog over finite structures of bounded treewidth. ACM Trans. Comput. Log. 12(1): 3 (2010)
(referuje Martin Koutecký)

Abstract: Namísto referování nových výsledků v článku se zaměříme především na v něm obsažený nový důkaz Courcellovy věty, která říká že formule v MSOL (monadické logice druhého řádu) je rozhodnutelná nad grafem (strukturou) s omezenou stromovou šířkou v lineárním čase.

15. 3., 22.3. 2011 (úterý [Tuesday], 8:30, MFF UK Malá Strana, S6)

Kevin P. Costello, Asaf Shapira, and Prasad Tetali: Randomized greedy: new variants of some classic approximation algorithms. SODA 2011.
(referuje Ondřej Zajíček)

Abstract: We consider the performance of two classic approximation algorithms which work by scanning the input and greedily constructing a solution. We investigate whether running these algorithms on a random permutation of the input can increase their performance ratio. We obtain the following results:
1. Johnson’s approximation algorithm for MAX-SAT is one of the first approximation algorithms to be rigorously analyzed. It has been shown that the performance ratio of this algorithm is 2/3. We show that when executed on a random permutation of the variables, the performance ratio of this algorithm is improved to 2/3 + c for some c > 0 This resolves an open problem of Chen, Friesen and Zhang [JCSS 1999]. (See also the paper by Poloczek and Schnitger in these proceedings for related results on this algorithm and its variants).
2. Motivated by the above improvement, we consider the performance of the greedy algorithm for MAXCUT whose performance ratio is 1/2. Our hope was that running the greedy algorithm on a random permutation of the vertices would result in a 1/2 + c approximation algorithm. However, it turns out that in this case the performance of the algorithm remains 1/2. This resolves an open problem of Mathieu and Schudy [SODA 2008].

1. 3., 8. 3. 2011 (úterý [Tuesday], 8:30, MFF UK Malá Strana, S6)

Davide Bilo, Luciano Guala and Guido Proietti: Improved approximability and non-approximability results for graph diameter decreasing problems. MFCS 2010.
(referuje Petr Kolman)

Abstract: In this paper we study two variants of the problem of adding edges to a graph so as to reduce the resulting diameter. More precisely, given a graph G = (V,E), and two positive integers D and B, the Minimum-Cardinality Bounded-Diameter Edge Addition (MCBD) problem is to find a minimum cardinality set F of edges to be added to G in such a way that the diameter of G+F is less than or equal to D, while the Bounded-Cardinality Minimum-Diameter Edge Addition (BCMD) problem is to find a set F of B edges to be added to G in such a way that the diameter of G+F is minimized. Both problems are well known to be NP-hard, as well as approximable within O(log n log D) and 4 (up to an additive term of 2), respectively. In this paper, we improve these longstanding approximation ratios to O(log n) and to 2 (up to an additive term of 2), respectively. As a consequence, we close, in an asymptotic sense, the gap on the approximability of the MCBD problem, which was known to be not approximable within c log n, for some constant c > 0, unless P = NP. Remarkably, as we further show in the paper, our approximation ratio remains asymptotically tight even if we allow for a solution whose diameter is optimal up to a multiplicative factor approaching 5/3. On the other hand, on the positive side, we show that at most twice of the minimal number of additional edges suffices to get at most twice of the required diameter.