Scheduling search procedures: The wheel of fortune

Scheduling search procedures: The wheel of fortune

0.00 Avg rating0 Votes
Article ID: iaor20081249
Country: United Kingdom
Volume: 9
Issue: 6
Start Page Number: 545
End Page Number: 557
Publication Date: Dec 2006
Journal: Journal of Scheduling
Authors:
Keywords: search, game theory
Abstract:

Suppose that a player can make progress on n jobs, and her goal is to complete a target job among them, as soon as possible. Unfortunately she does not know what the target job is, perhaps not even if the target exists. This is a typical situation in searching and testing. Depending on the player's prior knowledge and optimization goals, this gives rise to various optimization problems in the framework of game theory and, sometimes, competitive analysis. Continuing earlier work on this topic, we study another two versions. In the first game, the player knows only the job lengths and wants to minimize the completion time. A simple strategy that we call wheel-of-fortune (WOF) is optimal for this objective. A slight and natural modification, however, makes this game considerably more difficult: If the player can be sure that the target is present, WOF fails. However, we can still construct in polynomial time an optimal strategy based on WOF. We also prove that the tight absolute bounds on the expected search time. In the final part, we study two competitive-ratio minimization problems where either the job lengths or the target probabilities are known. We show their equivalence, describe the structure of optimal strategies, and give a heuristic solution.

Reviews

Required fields are marked *. Your email address will not be published.