Memory-restricted black-box complexity of One Max

被引：6
作者：
Doerr, Benjamin [1 ]
Winzen, Carola [1 ]
机构：
[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany
来源：
INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 1-2期
关键词：
Algorithms; Black-box complexity; Query complexity; Bounded memory;
D O I：
10.1016/j.ipl.2011.10.004
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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 Theta(n logn) conjecture of Droste, Jansen, and Wegener (Theory Computing Systems 39 (2006) 525-544). (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码：32 / 34
页数：3
相关论文
共 50 条
  • [21] Black-Box Search by Unbiased Variation
    Per Kristian Lehre
    Carsten Witt
    Algorithmica, 2012, 64 : 623 - 642
  • [22] Black-box complexities of combinatorial problems
    Doerr, Benjamin
    Koetzing, Timo
    Lengler, Johannes
    Winzen, Carola
    THEORETICAL COMPUTER SCIENCE, 2013, 471 : 84 - 106
  • [23] BLACK-BOX HAMILTONIAN SIMULATION AND UNITARY IMPLEMENTATION
    Berry, Dominic W.
    Childs, Andrew M.
    QUANTUM INFORMATION & COMPUTATION, 2012, 12 (1-2) : 29 - 62
  • [24] OneMax in Black-Box Models with Several Restrictions
    Carola Doerr
    Johannes Lengler
    Algorithmica, 2017, 78 : 610 - 640
  • [25] DISTRIBUTED BLACK-BOX OPTIMIZATION OF NONCONVEX FUNCTIONS
    Valcarcel Macua, Sergio
    Zazo, Santiago
    Zazo, Javier
    2015 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING (ICASSP), 2015, : 3591 - 3595
  • [26] ONEMAX in Black-Box Models with Several Restrictions
    Doerr, Carola
    Lengler, Johannes
    ALGORITHMICA, 2017, 78 (02) : 610 - 640
  • [27] OPENBOX: A Generalized Black-box Optimization Service
    Li, Yang
    Shen, Yu
    Zhang, Wentao
    Chen, Yuanwei
    Jiang, Huaijun
    Liu, Mingchao
    Jiang, Jiawei
    Gao, Jinyang
    Wu, Wentao
    Yang, Zhi
    Zhang, Ce
    Cui, Bin
    KDD '21: PROCEEDINGS OF THE 27TH ACM SIGKDD CONFERENCE ON KNOWLEDGE DISCOVERY & DATA MINING, 2021, : 3209 - 3219
  • [28] We might be afraid of black-box algorithms
    Veliz, Carissa
    Prunkl, Carina
    Phillips-Brown, Milo
    Lechterman, Theodore M.
    JOURNAL OF MEDICAL ETHICS, 2021, 47 (05) : 339 - 340
  • [29] On the Limits of Black-Box Reductions in Mechanism Design
    Chawla, Shuchi
    Immorlica, Nicole
    Lucier, Brendan
    STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2012, : 435 - 447
  • [30] Unbiased Black-Box Complexities of Jump Functions
    Doerr, Benjamin
    Doerr, Carola
    Koetzing, Timo
    EVOLUTIONARY COMPUTATION, 2015, 23 (04) : 641 - 670
12345