27 października 2015 10:15
[Seminarium ZOK]. Artur Kraska: A Randomized Algorithm for Online Scheduling with Interval Conflicts
Wtorek, 10:15-12:00, sala 310.
Abstract. In the contiguous variant of the Scheduling with Interval
Conflicts problem, there is a universe U consisting of elements being
consecutive positive integers. An input is a sequence of conflicts in the
form of intervals of length at most sigma. For each conflict, an algorithm has
to choose at most one surviving element, with the ultimate goal of maximizing
the number of elements that survived all conflicts. We present
an O(log sigma/ log log sigma)-competitive randomized algorithm for this problem,
beating known lower bound of Omega(log sigma) that holds for deterministic
algorithms.
This is a joint work with Marcin Bienkowski and Paweł Schmidt, published at SIROCCO 2015.