Memory-restricted black-box complexity of OneMax

Benjamin Doerr; Carola Winzen

doi:10.1016/j.ipl.2011.10.004

Memory-restricted black-box complexity of OneMax

Benjamin Doerr
, Carola Winzen

Max-Planck-Institut fur Informatik

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

We show that the black-box complexity with memory restriction one of the n-dimensional OneMax function class is at most 2n. This disproves the Θ(nlogn) conjecture of Droste, Jansen, and Wegener (Theory Computing Systems 39 (2006) 525-544).

langue originale	Anglais
Pages (de - à)	32-34
Nombre de pages	3
journal	Information Processing Letters
Volume	112
Numéro de publication	1-2
Les DOIs	https://doi.org/10.1016/j.ipl.2011.10.004
état	Publié - 15 janv. 2012
Modification externe	Oui

Accès au document

10.1016/j.ipl.2011.10.004

Contient cette citation

@article{f701a46f84f04acb9358ddf181a1a2e3,

title = "Memory-restricted black-box complexity of OneMax",

abstract = "We show that the black-box complexity with memory restriction one of the n-dimensional OneMax function class is at most 2n. This disproves the Θ(nlogn) conjecture of Droste, Jansen, and Wegener (Theory Computing Systems 39 (2006) 525-544).",

keywords = "Algorithms, Black-box complexity, Bounded memory, Query complexity",

author = "Benjamin Doerr and Carola Winzen",

year = "2012",

month = jan,

day = "15",

doi = "10.1016/j.ipl.2011.10.004",

language = "English",

volume = "112",

pages = "32--34",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "1-2",

}

TY - JOUR

T1 - Memory-restricted black-box complexity of OneMax

AU - Doerr, Benjamin

AU - Winzen, Carola

PY - 2012/1/15

Y1 - 2012/1/15

N2 - We show that the black-box complexity with memory restriction one of the n-dimensional OneMax function class is at most 2n. This disproves the Θ(nlogn) conjecture of Droste, Jansen, and Wegener (Theory Computing Systems 39 (2006) 525-544).

AB - We show that the black-box complexity with memory restriction one of the n-dimensional OneMax function class is at most 2n. This disproves the Θ(nlogn) conjecture of Droste, Jansen, and Wegener (Theory Computing Systems 39 (2006) 525-544).

KW - Algorithms

KW - Black-box complexity

KW - Bounded memory

KW - Query complexity

U2 - 10.1016/j.ipl.2011.10.004

DO - 10.1016/j.ipl.2011.10.004

M3 - Article

AN - SCOPUS:80054079731

SN - 0020-0190

VL - 112

SP - 32

EP - 34

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1-2

ER -

Memory-restricted black-box complexity of OneMax

Résumé

Accès au document

Empreinte digitale

Contient cette citation