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

Petr Kolman, Jiří Sgall

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

15. 5., 22. 5. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, S7)

Eden Chlamtac, Konstantin Makarychev, and Yury Makarychev: How to play unique games using embeddings. FOCS'06
(referuje Dušan Knop)

Abstract: In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states (labels), if a (1-eps) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1-O(eps*sqrt(log n log k)) fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size.

10. 4., 24. 4. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, S7)

Arman Yousefi and Neal Young: On a Linear Program for Minimum-Weight Triangulation. SODA 2012.
(referuje Martin Koutecký)

Abstract: Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial- time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: for an LP formulation due to Dantzig et al. (1985): (i) the integrality gap is bounded by a constant; (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP.

3. 4. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, S7)

Marc Thurle: An Approximation Algorithm for #k-SAT. STACS 2012.
(referuje Ondřej Zajíček)

Abstract: We present a simple randomized algorithm that approximates the number of satisfying assignments of Boolean formulas in conjunctive normal form. To the best of our knowledge this is the first algorithm which approximates #k-SAT for any k >= 3 within a running time that is not only non-trivial, but also significantly better than that of the currently fastest exact algorithms for the problem. More precisely, our algorithm is a randomized approximation scheme whose running time depends polynomially on the error tolerance and is mildly exponential in the number n of variables of the input formula. For example, even stipulating sub-exponentially small error tolerance, the number of solutions to 3-CNF input formulas can be approximated in time O(1.5366^n). For 4-CNF input the bound increases to O(1.6155^n).
We further show how to obtain upper and lower bounds on the number of solutions to a CNF formula in a controllable way. Relaxing the requirements on the quality of the approximation, on k-CNF input we obtain significantly reduced running times in comparison to the above bounds.

27. 3. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, S7)

Petr Kolman: Length-bounded cuts.

Abstract: Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in V$ and an integer parameter $L$, an {\em $L$-bounded cut} is a subset $F$ of edges such that the every path between $s$ and $t$ in $(V,E\setminus F)$ has length at least $L$. The task is to find an $L$-bounded cut of minimum cardinality. In the seminar I'll refer about a possible approach to the problem that is based on rounding a suitable LP relaxation.

13. 3., 20. 3. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, S7)

Sungjin Im, Maxim Sviridenko, and Ruben Van Der Zwaan: Preemptive and Non-Preemptive Generalized Min Sum Set Cover. STACS 2012.
(referuje Marek Krčál)

Abstract: In the (non-preemptive) Generalized Min Sum Set Cover Problem, we are given n ground elements and a collection of sets S = {S1, S2, ..., Sm} where each set S_i\in 2^[n] has a positive requirement kappa(Si) that has to be fulfilled. We would like to order all elements to minimize the total (weighted) cover time of all sets. The cover time of a set Si is defined as the first index j in the ordering such that the first j elements in the ordering contain kappa(Si) elements in Si. This problem was introduced by [1] with interesting motivations in web page ranking and broadcast scheduling. For this problem, constant approximations are known [2, 15].

We study the version where preemption is allowed. The difference is that elements can be fractionally scheduled and a set S is covered in the moment when kappa(S) amount of elements in S are scheduled. We give a 2-approximation for this preemptive problem. Our linear programming and analysis are completely different from [2, 15]. We also show that any preemptive solution can be transformed into a non-preemptive one by losing a factor of 6.2 in the objective function. As a byproduct, we obtain an improved 12.4-approximation for the non-preemptive problem.

28. 2., 6. 3. 2012 (úterý [Tuesday], 10:40, MFF UK Malá Strana, S7)

Lukasz Jez: Online interval scheduling on uniformly related machines.
(work in progress, joint with L. Epstein, J. Sgall, and R. van Stee)

Abstract:  Online interval scheduling was first studied by G. Weoginger [] in a single machine setting.  It is defined as follows: jobs (or intervals) of arbitrary lengths and values arrive over time and can be scheduled on the machine.  To be completed, the job has to be started upon arrival and be run until it completes (for the duration of its length).  The algorithm can stop processing any job at any time (and lose it) in order to start another.  The goal is to maximize the total value of completed jobs.

Woeginger observed that without restrictions on the jobs' lenghts and values, constant competitive ratio is impossible to attain.  With that in mind, he studied several special cases: that of unit length jobs of arbitrary values as well as so called f-related or f-benevolent instances, in which the value of the jobs is a function of its length, for convex and decreasing classes of functions.

We study an extension to uniformly related parallel machines, i.e., multiple machines that have different speeds.  As in the single machine case, to be completed, a job has to be run from its very arrival without any pauses, even though completing it will take different amount of time on different machines.  Except the variants mentioned above, we also study the cases of unit value jobs of arbitrary lengths and unit value jobs of unit lengths, both of which are no longer trivial in our setting