Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




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

URL of the conference:

http://www.sigevo.org/gecco-2012/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 01:01:08 PM
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