 |
|
|||
| Authors: | Hiroyuki Miyazawa, Thomas Erlebach |
| Group: | Theory of Communication Networks |
| Type: | Misc |
| Title: | A new randomized on-line algorithm for a weighted interval selection problem |
| Year: | 2001 |
| Month: | June |
| Pub-Key: | XME01 |
| Abstract: | Given a set of weighted intervals, the weighted interval selection problem (WISP) asks us to select a maximum-weight subset such that the selected intervals are pairwise disjoint. We consider
on-line algorithms that process the intervals in order of non-decreasing left endpoints. Preemption is allowed, but rejections are irrevocable. This problem has natural applications in various
scheduling problems.
When all the intervals have the same length, the best possible competitive ratio for deterministic on-line algorithms is 1/4. However, it has long been an open question whether there exists a randomized algorithm with better competitive ratio. In this paper, we present a new randomized algorithm and prove that it achieves a better competitive ratio 1/3 for a certain special case of WISP, thus giving the first result towards a solution of the long-unsolved open question. |
| Howpublished: | Workshop on Algorithms and Computation (WAAC). Pusan, Korea |
| Resources: | [BibTeX] |
