Search Results

Documents authored by Wegener, Ingo

Document
DOI: 10.4230/LIPIcs.STACS.2008.1348
Tight Bounds for Blind Search on the Integers

Authors: Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $mu$. More precisely, we show that $min_mu{E_mu(T)=Thetaleft((log n)^2 ight)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a ``blind'' optimization strategy.
Cite as

Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel. Tight Bounds for Blind Search on the Integers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 241-252, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dietzfelbinger_et_al:LIPIcs.STACS.2008.1348,
  author =	{Dietzfelbinger, Martin and Rowe, Jonathan E. and Wegener, Ingo and Woelfel, Philipp},
  title =	{{Tight Bounds for Blind Search on the Integers}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{241--252},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1348},
  URN =		{urn:nbn:de:0030-drops-13486},
  doi =		{10.4230/LIPIcs.STACS.2008.1348},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemRep.330
Theory of Evolutionary Algorithms (Dagstuhl Seminar 02031)

Authors: Hans-Georg Beyer, Kenneth A. De Jong, Colin Reeves, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Hans-Georg Beyer, Kenneth A. De Jong, Colin Reeves, and Ingo Wegener. Theory of Evolutionary Algorithms (Dagstuhl Seminar 02031). Dagstuhl Seminar Report 330, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{beyer_et_al:DagSemRep.330,
  author =	{Beyer, Hans-Georg and De Jong, Kenneth A. and Reeves, Colin and Wegener, Ingo},
  title =	{{Theory of Evolutionary Algorithms (Dagstuhl Seminar 02031)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{330},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.330},
  URN =		{urn:nbn:de:0030-drops-152137},
  doi =		{10.4230/DagSemRep.330},
}
Document
DOI: 10.4230/DagSemRep.265
Theory of Evolutionary Algorithms (Dagstuhl Seminar 00071)

Authors: Hans-Georg Beyer, Kenneth De Jong, David B. Fogel, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Hans-Georg Beyer, Kenneth De Jong, David B. Fogel, and Ingo Wegener. Theory of Evolutionary Algorithms (Dagstuhl Seminar 00071). Dagstuhl Seminar Report 265, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{beyer_et_al:DagSemRep.265,
  author =	{Beyer, Hans-Georg and De Jong, Kenneth and Fogel, David B. and Wegener, Ingo},
  title =	{{Theory of Evolutionary Algorithms (Dagstuhl Seminar 00071)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{265},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.265},
  URN =		{urn:nbn:de:0030-drops-151506},
  doi =		{10.4230/DagSemRep.265},
}
Document
DOI: 10.4230/DagSemRep.257
Complexity of Boolean Functions (Dagstuhl Seminar 99441)

Authors: D. M. Barrington, Rüdiger Reischuk, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

D. M. Barrington, Rüdiger Reischuk, and Ingo Wegener. Complexity of Boolean Functions (Dagstuhl Seminar 99441). Dagstuhl Seminar Report 257, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{barrington_et_al:DagSemRep.257,
  author =	{Barrington, D. M. and Reischuk, R\"{u}diger and Wegener, Ingo},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 99441)}},
  pages =	{1--30},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{257},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.257},
  URN =		{urn:nbn:de:0030-drops-151420},
  doi =		{10.4230/DagSemRep.257},
}
Document
DOI: 10.4230/DagSemRep.172
Complexity of Boolean Functions (Dagstuhl Seminar 9711)

Authors: David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener. Complexity of Boolean Functions (Dagstuhl Seminar 9711). Dagstuhl Seminar Report 172, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{barrington_et_al:DagSemRep.172,
  author =	{Barrington, David Mix and Nisan, Noam and Reischuk, R\"{u}diger and Wegener, Ingo},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 9711)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{172},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.172},
  URN =		{urn:nbn:de:0030-drops-150594},
  doi =		{10.4230/DagSemRep.172},
}
Document
DOI: 10.4230/DagSemRep.103
Neural Computing (Dagstuhl Seminar 9445)

Authors: Wolfgang Maass, Christoph von der Malsburg, Eduardo Sontag, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Wolfgang Maass, Christoph von der Malsburg, Eduardo Sontag, and Ingo Wegener. Neural Computing (Dagstuhl Seminar 9445). Dagstuhl Seminar Report 103, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1995)

Copy BibTex To Clipboard

@TechReport{maass_et_al:DagSemRep.103,
  author =	{Maass, Wolfgang and von der Malsburg, Christoph and Sontag, Eduardo and Wegener, Ingo},
  title =	{{Neural Computing (Dagstuhl Seminar 9445)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{1995},
  type = 	{Dagstuhl Seminar Report},
  number =	{103},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.103},
  URN =		{urn:nbn:de:0030-drops-149912},
  doi =		{10.4230/DagSemRep.103},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact