id: 05696513
dt: j
an: 05696513
au: Papakonstantinou, Periklis A.; Rackoff, Charles W.
ti: Characterizing sets of jobs that admit optimal greedy-like algorithms.
so: J. Sched. 13, No. 2, 163-176 (2010).
py: 2010
pu: Springer, Norwell, MA
la: EN
cc: 
ut: scheduling; interval scheduling; priority algorithms; optimal greedy
    algorithms; parallel scheduling
ci: Zbl 1082.68521
li: doi:10.1007/s10951-009-0148-2
ab: Summary: The “Priority Algorithm” is a model of computation introduced
    by {\it A. Borodin, M. N. Nielsen} and {\it C. Rackoff} [Algorithmica
    37, No. 4, 295‒326 (2003; Zbl 1082.68521)] which formulates a wide
    class of greedy algorithms. For an arbitrary set $\mathbb{S}$ of jobs,
    we are interested in whether or not there exists a priority algorithm
    that gains optimal profit on every subset of $\mathbb{S}$. In the case
    where the jobs are all intervals, we characterize such sets
    $\mathbb{S}$ and give an efficient algorithm (when $\mathbb{S}$ is
    finite) for determining this. We show that in general, however, the
    problem is NP-hard.
rv: