Flood search under the California Split rule

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

Research output: Contribution to journalArticle

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.

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

Keywords

  • 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

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

  • Cite this

    Baryshnikov, Y., Coffman, E., Jelenković, P., Momčilović, P., & Rubenstein, D. (2004). Flood search under the California Split rule. Operations Research Letters, 32(3), 199-206. https://doi.org/10.1016/j.orl.2003.08.007