| Article ID: | iaor20043279 |
| Country: | Netherlands |
| Volume: | 32 |
| Issue: | 3 |
| Start Page Number: | 199 |
| End Page Number: | 206 |
| Publication Date: | May 2004 |
| Journal: | Operations Research Letters |
| Authors: | Coffman E., Baryshnikov Y., Jelenkovi P., Momilovi P., Rubenstein D. |
| Keywords: | off-line algorithm |
We consider flood search on a line and show that no algorithm can achieve an average-case competitive ratio of less than 4 when compared to the optimal off-line algorithm. We also demonstrate that the optimal scanning sequences are described by simple recursive relationships that yield surprisingly complex behavior related to Hamiltonian chaos.