Zobrazeno 1 - 10
of 59
pro vyhledávání: '"Winzen, Carola"'
Autor:
Doerr, Benjamin, Winzen, Carola
We show that the unrestricted black-box complexity of the $n$-dimensional XOR- and permutation-invariant LeadingOnes function class is $O(n \log (n) / \log \log n)$. This shows that the recent natural looking $O(n\log n)$ bound is not tight. The blac
Externí odkaz:
http://arxiv.org/abs/1210.6465
We analyze the network congestion game with atomic players, asymmetric strategies, and the maximum latency among all players as social cost. This important social cost function is much less understood than the average latency. We show that the price
Externí odkaz:
http://arxiv.org/abs/1210.0230
Autor:
Doerr, Benjamin, Winzen, Carola
We show that for all $1
Externí odkaz:
http://arxiv.org/abs/1203.4111
Autor:
Doerr, Benjamin, Winzen, Carola
We analyze the classic board game of Mastermind with $n$ holes and a constant number of colors. A result of Chv\'atal (Combinatorica 3 (1983), 325-329) states that the codebreaker can find the secret code with $\Theta(n / \log n)$ questions. We show
Externí odkaz:
http://arxiv.org/abs/1110.3619
Black-box complexity is a complexity theoretic measure for how difficult a problem is to be optimized by a general purpose optimization algorithm. It is thus one of the few means trying to understand which problems are tractable for genetic algorithm
Externí odkaz:
http://arxiv.org/abs/1108.0342
Autor:
Winzen, Carola
In a recent work, Doerr and Fouz [\emph{Asymptotically Optimal Randomized Rumor Spreading}, in ArXiv] present a new quasi-random PUSH algorithm for the rumor spreading problem (also known as gossip spreading or message propagation problem). Their \em
Externí odkaz:
http://arxiv.org/abs/1103.2429
Publikováno v:
SIAM Journal of Numerical Analysis 50, 781-807, 2012
We present a new algorithm for estimating the star discrepancy of arbitrary point sets. Similar to the algorithm for discrepancy approximation of Winker and Fang [SIAM J. Numer. Anal. 34 (1997), 2028--2042] it is based on the optimization algorithm t
Externí odkaz:
http://arxiv.org/abs/1103.2102
Autor:
Doerr, Benjamin, Winzen, Carola
Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing f
Externí odkaz:
http://arxiv.org/abs/1102.1140
Publikováno v:
Algorithmica, 2012, Volume 64, Issue 4, pp 673-697
In this work, we introduce multiplicative drift analysis as a suitable way to analyze the runtime of randomized search heuristics such as evolutionary algorithms. We give a multiplicative version of the classical drift theorem. This allows easier ana
Externí odkaz:
http://arxiv.org/abs/1101.0776
Autor:
Doerr, Benjamin, Johannsen, Daniel, Kötzing, Timo, Lehre, Per Kristian, Wagner, Markus, Winzen, Carola
We extend the work of Lehre and Witt (GECCO 2010) on the unbiased black-box model by considering higher arity variation operators. In particular, we show that already for binary operators the black-box complexity of \leadingones drops from $\Theta(n^
Externí odkaz:
http://arxiv.org/abs/1012.0952