CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Scheduling search procedures

Peter Damaschke (Institutionen för datavetenskap, Bioinformatik ; Institutionen för datavetenskap, Algoritmer)
Journal of Scheduling (1094-6136). Vol. 7 (2004), 5, p. 349-364.
[Artikel, refereegranskad vetenskaplig]

We analyze preemptive on-line scheduling against randomized adversaries, with the goal to finish an unknown distinguished target job. Our motivation comes from clinical gene search projects, but the subject leads to general theoretical questions of independent interest, including some natural but unusual probabilistic models. We study problem versions with known and unknown processing times of jobs and target probabilities, and models where the on-line player gets some randomized extra information about the target. For some versions we get optimal competitive ratios, expressed in terms of given parameters of instances.

Nyckelord: on-line algorithms, randomized adversary, searching, Bayesian models

Denna post skapades 2006-09-25. Senast ändrad 2015-02-11.
CPL Pubid: 1617


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Bioinformatik (2002-2004)
Institutionen för datavetenskap, Algoritmer (2002-2004)


Information Technology

Chalmers infrastruktur