On the structure of optimal greedy computation (for job scheduling)

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider Priority Algorithm [4] as a syntactic model of formulating the concept of greedy algorithm for Job Scheduling, and we study the computation of optimal priority algorithms. A Job Scheduling subproblem is S determined by a (possibly infinite) set of jobs, every finite subset of which potentially forms an input to a scheduling algorithm. An algorithm is optimal for S, if it gains optimal profit on every input. To the best of our knowledge there is no previous work about such arbitrary subproblems of Job Scheduling. For a finite , it is coNP-hard to decide whether S admits an optimal priority algorithm [12]. This indicates that meaningful characterizations of subproblems admitting optimal priority algorithms may not be possible. In this paper we consider those S that do admit optimal priority algorithms, and we show that the way in which all such algorithms compute has non-trivial and interesting structural features.

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
Pages612-623
Number of pages12
DOIs
StatePublished - 2009
Externally publishedYes
Event34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 - Novy Smokovec, High Tatras, Slovakia
Duration: Aug 24 2009Aug 28 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5734 LNCS

Other

Other34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
Country/TerritorySlovakia
CityNovy Smokovec, High Tatras
Period8/24/098/28/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On the structure of optimal greedy computation (for job scheduling)'. Together they form a unique fingerprint.

Cite this