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)
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.
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 [http://dx.doi.org/10.1016/0304-3975(94)90150-3] 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