Mathematik-Gebäude, Seminarraum M921

We present complexity results and online algorithms for a new version of interval scheduling, which is a classical problem in operations research and combinatorial optimization.
In the version of the problem we consider, n intervals (jobs with fixed starting times) have to be scheduled on m machines with different speeds with the objective to maximize the number of accepted intervals.
We prove that the offline version of the problem is strongly NP-hard to solve. For the online version, we show a lower bound of 5/3 on the competitive ratio of any deterministic online algorithm for the problem.
Moreover, we present two simple greedy rules for online algorithms and show that any online algorithm using these rules is 2-competitive. One of these 2-competitive algorithms is shown to run in O(n log m) time.
Additionally, we prove that our greedy rules impose no loss in the sense that every online algorithm for the problem can be modified to use the rules without reducing the number of accepted intervals on any instance.

Dr. Clemens Thielen

TU Kaiserslautern