Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.orl.2003.08.007 | Oper. Res. Lett. |
Keywords | Field | DocType |
competitive analysis | Mathematical optimization,Hamiltonian (quantum mechanics),Flood myth,Recursion,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
32 | 3 | 0167-6377 |
Citations | PageRank | References |
17 | 1.47 | 10 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuliy Baryshnikov | 1 | 135 | 22.05 |
Edward G. Coffman Jr. | 2 | 2028 | 1442.37 |
Predrag R. Jelenkovic | 3 | 219 | 29.99 |
Petar Momcilovic | 4 | 93 | 12.28 |
Dan Rubenstein | 5 | 289 | 17.02 |