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

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

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

Original language	English
Pages (from-to)	32-34
Number of pages	3
Journal	Information Processing Letters
Volume	112
Issue number	1-2
DOIs	https://doi.org/10.1016/j.ipl.2011.10.004
Publication status	Published - 15 Jan 2012
Externally published	Yes

Keywords

Algorithms
Black-box complexity
Bounded memory
Query complexity

Access to Document

10.1016/j.ipl.2011.10.004

Cite this

@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

Abstract

Keywords

Access to Document

Fingerprint

Cite this