•
Assume all-or-nothing problems
•
•
Goal: Minimize expected delay for reaching complete
solutions to challenges posed in the next period(s)
•
Theorem: Idle-Time Partition
The optimal policy is to spend available idle time
solving future problems completely, in order of their
probability.
Minimizing Computational Delay
p( I
1
| E )
p( I
n
| E )
p( I
2
| E )
p( I
3
| E )
p( I
n
| E ) > p( I
n+1
| E )
p( I
1
| E )
p( I
2
| E )
p( I
3
| E )
p( I
n
| E )
Eric Horvitz, April 5, 2003