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 Complexities of Combinatorial Problems [J].

Doerr, Benjamin ;

Koetzing, Timo ;

Lengler, Johannes ;

Winzen, Carola .

GECCO-2011: PROCEEDINGS OF THE 13TH ANNUAL GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2011, :981-988

[22] Black-box complexities of combinatorial problems [J].

Doerr, Benjamin ;

Koetzing, Timo ;

Lengler, Johannes ;

Winzen, Carola .

THEORETICAL COMPUTER SCIENCE, 2013, 471 :84-106

[23] Black-box Methods for Restoring Monotonicity [J].

Gergatsouli, Evangelia ;

Lucier, Brendan ;

Tzamos, Christos .

INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 119, 2020, 119

[24] BLACK-BOX HAMILTONIAN SIMULATION AND UNITARY IMPLEMENTATION [J].

Berry, Dominic W. ;

Childs, Andrew M. .

QUANTUM INFORMATION & COMPUTATION, 2012, 12 (1-2) :29-62

[25] OneMax in Black-Box Models with Several Restrictions [J].

Carola Doerr ;

Johannes Lengler .

Algorithmica, 2017, 78 :610-640

[26] DISTRIBUTED BLACK-BOX OPTIMIZATION OF NONCONVEX FUNCTIONS [J].

Valcarcel Macua, Sergio ;

Zazo, Santiago ;

Zazo, Javier .

2015 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH, AND SIGNAL PROCESSING (ICASSP), 2015, :3591-3595

[27] ONEMAX in Black-Box Models with Several Restrictions [J].

Doerr, Carola ;

Lengler, Johannes .

ALGORITHMICA, 2017, 78 (02) :610-640

[28] OPENBOX: A Generalized Black-box Optimization Service [J].

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

[29] We might be afraid of black-box algorithms [J].

Veliz, Carissa ;

Prunkl, Carina ;

Phillips-Brown, Milo ;

Lechterman, Theodore M. .

JOURNAL OF MEDICAL ETHICS, 2021, 47 (05) :339-340

[30] On the Limits of Black-Box Reductions in Mechanism Design [J].

Chawla, Shuchi ;

Immorlica, Nicole ;

Lucier, Brendan .

STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2012, :435-447

← 1 2 3 4 5 →