next up previous
Next: 4.1 Counterexample for routing Up: Packet Routing and Job-Shop Previous: 3.2 The main result

4 Counterexamples to on-line algorithms


This section presents examples where several natural on-line scheduling strategies do poorly. Based on these examples, we suspect that finding an on-line algorithm that can schedule any set of paths in tex2html_wrap_inline2100 steps using constant-size queues will be a challenging task.

Bruce Maggs
Mon Jul 22 20:27:47 EDT 1996