Author name cluster

Nils Hebbinghaus

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

TCS Journal 2010 Journal Article

Plateaus can be harder in multi-objective optimization

Tobias Friedrich
Nils Hebbinghaus
Frank Neumann

In recent years a lot of progress has been made in understanding the behavior of evolutionary computation methods for single- and multi-objective problems. Our aim is to analyze the diversity mechanisms that are implicitly used in evolutionary algorithms for multi-objective problems by rigorous runtime analyses. We show that, even if the population size is small, the runtime can be exponential where corresponding single-objective problems are optimized within polynomial time. To illustrate this behavior we analyze a simple plateau function in a first step and extend our result to a class of instances of the well-known SetCover problem.

Details DOI

TCS Journal 2009 Journal Article

Comparison of simple diversity mechanisms on plateau functions

Tobias Friedrich
Nils Hebbinghaus
Frank Neumann

It is widely assumed and observed in experiments that the use of diversity mechanisms in evolutionary algorithms may have a great impact on its running time. Up to now there is no rigorous analysis pointing out how different diversity mechanisms influence the runtime behavior. We consider evolutionary algorithms that differ from each other in the way they ensure diversity and point out situations where the right mechanism is crucial for the success of the algorithm. The considered evolutionary algorithms either diversify the population with respect to the search points or with respect to function values. Investigating simple plateau functions, we show that using the “right” diversity strategy makes the difference between an exponential and a polynomial runtime. Later on, we examine how the drawback of the “wrong” diversity mechanism can be compensated by increasing the population size.

Details DOI

TCS Journal 2006 Journal Article

Improved bounds and schemes for the declustering problem

Benjamin Doerr
Nils Hebbinghaus
Sören Werth

The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. Using deep results from discrepancy theory, we improve previous work of several authors concerning range queries to higher-dimensional data. We give a declustering scheme with an additive error of O d ( log d - 1 M ) independent of the data size, where d is the dimension, M the number of storage devices and d - 1 does not exceed the smallest prime power in the canonical decomposition of M into prime powers. In particular, our schemes work for arbitrary M in dimensions two and three. For general d, they work for all M ⩾ d - 1 that are powers of two. Concerning lower bounds, we show that a recent proof of a Ω d ( log ( d - 1 ) / 2 M ) bound contains an error. We close the gap in the proof and thus establish the bound.

Details DOI

MFCS Conference 2004 Conference Paper

Improved Bounds and Schemes for the Declustering Problem

Benjamin Doerr
Nils Hebbinghaus
Sören Werth

Abstract The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed among the devices. Using deep results from discrepancy theory, we improve previous work of several authors concerning rectangular queries of higher-dimensional data. For this problem, we give a declustering scheme with an additive error of O d (log d − 1 M ) independent of the data size, where d is the dimension, M the number of storage devices and d -1 not larger than the smallest prime power in the canonical decomposition of M. Thus, in particular, our schemes work for arbitrary M in two and three dimensions, and arbitrary M ≥ d -1 that is a power of two. These cases seem to be the most relevant in applications. For a lower bound, we show that a recent proof of a \(\Omega_d(\log^{\frac{d-1}{2}} M)\) bound contains a critical error. Using an alternative approach, we establish this bound.

Details