Flood search under the California Split rule

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

doi:10.1016/j.orl.2003.08.007

Flood search under the California Split rule

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

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	199-206
Number of pages	8
Journal	Operations Research Letters
Volume	32
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2003.08.007
State	Published - May 2004
Externally published	Yes

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

Online availability

10.1016/j.orl.2003.08.007

Library availability

Discover UIUC Full Text

Cite this

@article{615488cf80d7462c9aa965a01a1e74e6,

title = "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.",

keywords = "Average case competitive analysis, Expanding ring, Flood search, Peer-to-peer systems",

author = "Y. Baryshnikov and E. Coffman and P. Jelenkovi{\'c} and P. Mom{\v c}ilovi{\'c} and D. Rubenstein",

year = "2004",

month = may,

doi = "10.1016/j.orl.2003.08.007",

language = "English (US)",

volume = "32",

pages = "199--206",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Flood search under the California Split rule

AU - Baryshnikov, Y.

AU - Coffman, E.

AU - Jelenković, P.

AU - Momčilović, P.

AU - Rubenstein, D.

PY - 2004/5

Y1 - 2004/5

N2 - 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.

AB - 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.

KW - Average case competitive analysis

KW - Expanding ring

KW - Flood search

KW - Peer-to-peer systems

UR - http://www.scopus.com/inward/record.url?scp=0346280063&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346280063&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2003.08.007

DO - 10.1016/j.orl.2003.08.007

M3 - Article

AN - SCOPUS:0346280063

SN - 0167-6377

VL - 32

SP - 199

EP - 206

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

Flood search under the California Split rule

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this