Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Improved Randomized Online Scheduling of Unit Length Intervals and Jobs
verfasst von : Stanley P. Y. Fung, Chung Keung Poon, Feifeng Zheng
Erschienen in: Approximation and Online Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the online interval scheduling problem and the online job scheduling problem (with restart). In both problems, the intervals or jobs have unit length and arbitrary weights, and the objective is to maximize the total weight of completed intervals (or jobs). We first gave a 2-competitive randomized algorithm for the case of intervals. The algorithm is barely random in the sense that it randomly chooses between two deterministic algorithms at the beginning and then sticks with it thereafter. The algorithm is surprisingly simple and improves upon several previous results. Then we extended the algorithm to the scheduling of jobs with restarts, and proved that it is 3-competitive. We also proved a lower bound of 2 on the competitive ratio of all barely random algorithms that choose between two deterministic algorithms for scheduling intervals (and jobs).