Flood search under the California Split rule

abstract

• The flood searching algorithm, under the California Split rule, was studied. The flood search on a line indicated that no algorithm was capable of achieving an average-case competitive ratio of less than 4 in comparison to an optimal off-line algorithm. The study described the employed optimal scanning sequences. The sequences were obtained via recursive algorithms, which yield to complex behavior related to Hamiltonian chaos.

authors

• Momcilovic, Petar

published proceedings

• OPERATIONS RESEARCH LETTERS

author list (cited authors)

• Baryshnikov, Y., Coffman, E., Jelenkovic, P., Momcilovic, P., & Rubenstein, D.

citation count

• 22

complete list of authors

• Baryshnikov, Y||Coffman, E||Jelenkovic, P||Momcilovic, P||Rubenstein, D

publication date

• January 2004

publisher

• Elsevier  Publisher

published in

• Operations Research Letters  Journal

keywords

• Average Case Competitive Analysis
• Expanding Ring
• Flood Search
• Peer-to-peer Systems

Digital Object Identifier (DOI)

• 10.1016/j.orl.2003.08.007

start page

• 199

end page

• 206

volume

• 32

issue

• 3

URL

• http://dx.doi.org/10.1016/j.orl.2003.08.007