Output details
11 - Computer Science and Informatics
University of Leicester
Article title
Online Interval Scheduling: Randomized and Multiprocessor Cases
Type
D - Journal article
Title of journal
Journal of Combinatorial Optimization
Article number
-
Volume number
16
Issue number
3
First page of article
248
ISSN of journal
1382-6905
Year of publication
2008
URL
-
Number of additional authors
2
Additional information
<12>The problem considered here was first raised by Woeginger (TCS 1994) and remained completely open until this paper. We give the first positive result: a randomized algorithm with a better competitive ratio than deterministic algorithms. It led to renewed interest in the problem (and its variants) and several subsequent papers have since appeared (Epstein and Levin ESA'08, Fung et al WAOA'08, Epstein et al APPROX-RANDOM'12.) The barely random lower bound of 2 in the paper directly inspired the currently best algorithm (WAOA'08); the currently best lower bound (ESA'08) is a combination of techniques in TCS'94 and this paper.
Interdisciplinary
-
Cross-referral requested
-
Research group
None
Citation count
5
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
