Flood search under the California Split rule

Y. Baryshnikov, E. Coffman, P. Jelenković, P. Momčilović, D. Rubenstein

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)199-206
Number of pages8
JournalOperations Research Letters
Issue number3
StatePublished - May 1 2004
Externally publishedYes


  • Average case competitive analysis
  • Expanding ring
  • Flood search
  • Peer-to-peer systems

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


Dive into the research topics of 'Flood search under the California Split rule'. Together they form a unique fingerprint.

Cite this