MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Winzen, Carola		dblp
dblp
Editor(s):
Soule, Terence
Moore, Jason H.		dblp
dblp
Not MPII Editor(s):
Soule, Terence
Moore, Jason H.
BibTeX cite key*:
DoerrW12GECCO
Title, Booktitle
Title*:
Reducing the arity in unbiased black-box complexity
Booktitle*:
GECCO'12 : Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation
Event, URLs
Conference URL::
http://www.sigevo.org/gecco-2012/
Downloading URL:
http://dl.acm.org/citation.cfm?doid=2330163.2330345
Event Address*:
Philadelphia, PA
Language:
English
Event Date*
(no longer used):
Organization:
Association for Computing Machinery (ACM)
Event Start Date:
7 December 2012
Event End Date:
7 December 2012
Publisher
Name*:
ACM
URL:
http://www.acm.org/
Address*:
New York, NY
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
1309-1316
Year*:
2012
VG Wort Pages:
31
ISBN/ISSN:
978-1-4503-1177-9
Sequence Number:
DOI:
10.1145/2330163.2330345
Note, Abstract, ©
(LaTeX) Abstract:
We show that for all $1<k \leq \log n$ the $k$-ary unbiased black-box complexity of the $n$-dimensional $\onemax$ function class is $O(n/k)$.
This indicates that the power of higher arity operators is much stronger than what the previous $O(n/\log k)$ bound by Doerr et al. (Faster black-box algorithms through higher arity operators, Proc. of FOGA 2011, pp. 163--172, ACM, 2011) suggests.

The key to this result is an encoding strategy, which might be of
independent interest. We show that, using $k$-ary unbiased variation
operators only, we may simulate an unrestricted memory of
size $O(2^k)$ bits.
Keywords:
Black-box complexity, running time analysis, theory
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrW12GECCO,
AUTHOR = {Doerr, Benjamin and Winzen, Carola},
 EDITOR = {Soule, Terence and Moore, Jason H.},
 TITLE = {Reducing the arity in unbiased black-box complexity},
 BOOKTITLE = {GECCO'12 : Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation},
 PUBLISHER = {ACM},
 YEAR = {2012},
 ORGANIZATION = {Association for Computing Machinery (ACM)},
 PAGES = {1309--1316},
 ADDRESS = {Philadelphia, PA},
 ISBN = {978-1-4503-1177-9},
 DOI = {10.1145/2330163.2330345},
}

Entry last modified by Uwe Brahm, 02/01/2013
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
12/07/2012 13:01:08
Revisions
6.
5.
4.
3.
2.		Editor(s)
Uwe Brahm
Uwe Brahm
Anja Becker
Benjamin Doerr
Benjamin Doerr		Edit Dates
01-02-2013 03:03:24 PM
01-02-2013 02:59:13 PM
30.01.2013 13:11:48
01/11/2013 01:38:26 PM
12.12.2012 14:32:44