One-pass algorithms with revocable acceptances for job interval selection.
Published: 2004
Language: eng
Number of pages: 67
Description: In this research, one-pass algorithms are considered for the weighted job interval selection problem on m machines (WJISP m). One-pass algorithms with revocable acceptances consider each input once, and must accept or reject the input at that time. At any instant, the set of accepted intervals must be a feasible solution to the problem; however, previously accepted intervals can be later rejected to maintain this condition.In this thesis, an algorithm called ONE-PASS W EIGHT/LENGTHalpha is presented and analyzed. This algorithm gives constant approximation ratios for the general WJISPm and many variants. Secondly, this work shows that no adaptive one-pass algorithm with revocable acceptances can have an approximation ratio smaller than 1.17 for weighted interval selection on one machine, even when all interval lengths are the same. This shows that one-pass algorithms with revocable acceptances cannot optimally solve the interval selection problem on one machine.
Notes: Adviser: Allan Borodin.

Thesis (M.Sc.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 42-06, page: 2232.

MICR copy on microfiche (1 microfiche).