Ingo Wegener
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Ingo Wegener has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Thomas Jansen
Aberystwyth University
4 shared publications - Beate Bollig
FB Informatik, LS2, University of Dortmund, 44221 Dortmund, Germany
2 shared publications - Jaikumar Radhakrishnan
Tata Institute of Fundamental Research Mumbai India
2 shared publications Jens Scharnow
University of Dortmund
2 shared publicationsKarsten Tinnefeld
University of Dortmund
2 shared publicationsMartin Sauerhoff
FB Informatik, LS 2, Univ. Dortmund, Dortmund, 44221, Germany
2 shared publications
Latest Publications
- 1 June 2006
- Published by Springer Nature in Statistics and Computing
- Vol. 16 (2) , 177-192
Modified repeated median filters
- 1 June 2006
- Published by Springer Nature in Statistics and Computing
- Vol. 16 (2) , 177-192
Modified repeated median filters
- Open Access
- 30 November 2005
- Published by Elsevier in Theoretical Computer Science
- Vol. 347 (1-2) , 325-335
On converting CNF to DNF
- 30 November 2005
- Published by Elsevier in Theoretical Computer Science
- Vol. 347 (1-2) , 325-335
Open AccessOn converting CNF to DNF
- 2 February 2005
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 4 (1) , 181-199
On the analysis of a dynamic evolutionary algorithm
- 2 February 2005
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 4 (1) , 181-199
On the analysis of a dynamic evolutionary algorithm
- 1 January 2005
- Published by Springer Nature in Journal of Mathematical Modelling and Algorithms
- Vol. 3 (4) , 349-366
The analysis of evolutionary algorithms on sorting and shortest paths problems
- 1 January 2005
- Published by Springer Nature in Journal of Mathematical Modelling and Algorithms
- Vol. 3 (4) , 349-366
The analysis of evolutionary algorithms on sorting and shortest paths problems
- 1 January 2005
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 14 (1-2) , 225-247
On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics
Randomized search heuristics like evolutionary algorithms and simulated annealing find many applications, especially in situations where no full information on the problem instance is available. In order to understand how these heuristics work, it is necessary to analyse their behaviour on classes of functions. Such an analysis is performed here for the class of monotone pseudo-Boolean polynomials. Results depending on the degree and the number of terms of the polynomial are obtained. The class of monotone polynomials is of special interest since simple functions of this kind can have an image set of exponential size, improvements can increase the Hamming distance to the optimum and, in order to find a better search point, it can be necessary to search within a large plateau of search points with the same fitness value.
- 1 January 2005
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 14 (1-2) , 225-247
On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics
Randomized search heuristics like evolutionary algorithms and simulated annealing find many applications, especially in situations where no full information on the problem instance is available. In order to understand how these heuristics work, it is necessary to analyse their behaviour on classes of functions. Such an analysis is performed here for the class of monotone pseudo-Boolean polynomials. Results depending on the degree and the number of terms of the polynomial are obtained. The class of monotone polynomials is of special interest since simple functions of this kind can have an image set of exponential size, improvements can increase the Hamming distance to the optimum and, in order to find a better search point, it can be necessary to search within a large plateau of search points with the same fitness value.
- 1 December 2004
- Published by Springer Nature in Journal of Mathematical Modelling and Algorithms
- Vol. 3 (4) , 349-366
The Analysis of Evolutionary Algorithms on Sorting and Shortest Paths Problems
- 1 December 2004
- Published by Springer Nature in Journal of Mathematical Modelling and Algorithms
- Vol. 3 (4) , 349-366
The Analysis of Evolutionary Algorithms on Sorting and Shortest Paths Problems
- Top Cited Papers
- 16 November 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 39 (4) , 525-544
Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization
- 16 November 2004
- Published by Springer Nature in Theory of Computing Systems
- Vol. 39 (4) , 525-544
Top Cited PapersUpper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization
- Open Access
- 15 June 2003
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 10 (45)
On converting CNF to DNF
We study how big the blow-up in size can be when one switches between the CNF and DNF representations of boolean functions. For a function f : {0,1}^n -> {0,1}, cnfsize(f) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize(f) denotes the minimum number of terms in a DNF for f. For 0 <= m <= 2^{n-1} , let dnfsize(m,n) be the maximum dnfsize(f) for a function f : {0,1}^n -> {0,1} with cnfsize(f) <= m. We show that there are constants c_1, c_2 >= 1 and epsilon > 0 , such that for all large n and all m in [ 1/epsilon n , 2^{epsilon n}], we have 2^{(n - c_1) n / log(m/n)} <= dnfsize(m,n) <= 2^{(n - c_2) n / log(m/n)}. In particular, when m is the polynomial n^c, we get dnfsize(n^c,n) = 2^{(n - theta) (c^{-1} n / log n)}.
- 15 June 2003
- Published by Det Kgl. Bibliotek/Royal Danish Library in BRICS Report Series
- Vol. 10 (45)
Open AccessOn converting CNF to DNF
We study how big the blow-up in size can be when one switches between the CNF and DNF representations of boolean functions. For a function f : {0,1}^n -> {0,1}, cnfsize(f) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize(f) denotes the minimum number of terms in a DNF for f. For 0 <= m <= 2^{n-1} , let dnfsize(m,n) be the maximum dnfsize(f) for a function f : {0,1}^n -> {0,1} with cnfsize(f) <= m. We show that there are constants c_1, c_2 >= 1 and epsilon > 0 , such that for all large n and all m in [ 1/epsilon n , 2^{epsilon n}], we have 2^{(n - c_1) n / log(m/n)} <= dnfsize(m,n) <= 2^{(n - c_2) n / log(m/n)}. In particular, when m is the polynomial n^c, we get dnfsize(n^c,n) = 2^{(n - theta) (c^{-1} n / log n)}.
- 1 January 2003
- Published by Springer Nature
- p. 123-134
Die Komplexität von Black-Box-Problemen
- 1 January 2003
- Published by Springer Nature
- p. 105-121
Die Komplexität von Approximationsproblemen — klassische Resultate
- 1 January 2003
- Published by Springer Nature
- p. 105-121
Die Komplexität von Approximationsproblemen — klassische Resultate