Search Results

Documents authored by Vöcking, Berthold

Document
DOI: 10.4230/DagRep.3.11.58
Electronic Markets and Auctions (Dagstuhl Seminar 13461)

Authors: Yishay Mansour, Benny Moldovanu, Noam Nisan, and Berthold Vöcking

Published in: Dagstuhl Reports, Volume 3, Issue 11 (2014)

Abstract
The main goal of this workshop was to study topics related to electronic markets and auctions both from the computational perspective and from a game-theoretic and economic one. From the computer science perspective, with the advent of the Internet, there has been a significant amount of work in Algorithmic Game Theory focusing on computational aspects of electronic markets and on algorithmic aspects of mechanism design. Economics have been traditionally interested in markets in general and designing efficient markets mechanisms (such as auctions) in particular. The recent emergence of electronic markets and auctions has only reemphasized the importance of this topic.
Cite as

Yishay Mansour, Benny Moldovanu, Noam Nisan, and Berthold Vöcking. Electronic Markets and Auctions (Dagstuhl Seminar 13461). In Dagstuhl Reports, Volume 3, Issue 11, pp. 58-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{mansour_et_al:DagRep.3.11.58,
  author =	{Mansour, Yishay and Moldovanu, Benny and Nisan, Noam and V\"{o}cking, Berthold},
  title =	{{Electronic Markets and Auctions (Dagstuhl Seminar 13461)}},
  pages =	{58--78},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{11},
  editor =	{Mansour, Yishay and Moldovanu, Benny and Nisan, Noam and V\"{o}cking, Berthold},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.11.58},
  URN =		{urn:nbn:de:0030-drops-44379},
  doi =		{10.4230/DagRep.3.11.58},
  annote =	{Keywords: Algorithmic game theory, mechanism design, economics, electronic markets}
}
Document
DOI: 10.4230/DagSemProc.10211.1
10211 Abstracts Collection – Flexible Network Design

Authors: Anupam Gupta, Stefano Leonardi, Berthold Vöcking, and Roger Wattenhofer

Published in: Dagstuhl Seminar Proceedings, Volume 10211, Flexible Network Design (2010)

Abstract
From Monday 24.05.2010---Friday 28.05.2010, the Dagstuhl Seminar 10211 ``Flexible Network Design '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Anupam Gupta, Stefano Leonardi, Berthold Vöcking, and Roger Wattenhofer. 10211 Abstracts Collection – Flexible Network Design. In Flexible Network Design. Dagstuhl Seminar Proceedings, Volume 10211, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:DagSemProc.10211.1,
  author =	{Gupta, Anupam and Leonardi, Stefano and V\"{o}cking, Berthold and Wattenhofer, Roger},
  title =	{{10211 Abstracts Collection – Flexible Network Design}},
  booktitle =	{Flexible Network Design},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10211},
  editor =	{Anupam Gupta and Stefano Leonardi and Berthold V\"{o}cking and Roger Wattenhofer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10211.1},
  URN =		{urn:nbn:de:0030-drops-27279},
  doi =		{10.4230/DagSemProc.10211.1},
  annote =	{Keywords: Network Design, Approximation Algorithms, Game Theory and Mechanism Design, Wireless Networks}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1826
Economical Caching

Authors: Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain capacity. For each time step, an online algorithm is given a price from the interval $[1,\alpha]$, a consumption, and possibly a buying limit. The online algorithm has to decide the amount to purchase from some commodity, knowing the parameter $\alpha$ but without knowing how the price evolves in the future. The algorithm can purchase at most the buying limit. If it purchases more than the current consumption, then the excess is stored in the storage; otherwise, the gap between consumption and purchase must be taken from the storage. The goal is to minimize the total cost. Interesting applications are, for example, stream caching on mobile devices with different classes of service, battery management in micro hybrid cars, and the efficient purchase of resources. First we consider the simple but natural class of algorithms that can informally be described as memoryless. We show that these algorithms cannot achieve a competitive ratio below $\sqrt{\alpha}$. Then we present a more sophisticated deterministic algorithm achieving a competitive ratio of \[\textstyle \frac{1}{W\left(\frac{1-\alpha}{e\alpha}\right)+1} \in \left[\frac{\sqrt{\alpha}}{\sqrt{2}}, \frac{\sqrt{\alpha}+1}{\sqrt{2}} \right] \enspace, \] where $W$ denotes the Lambert~W function. We prove that this algorithm is optimal and that not even randomized online algorithms can achieve a better competitive ratio. On the other hand, we show how to achieve a constant competitive ratio if the storage capacity of the online algorithm exceeds the storage capacity of an optimal offline algorithm by a factor of $\log \alpha$.
Cite as

Matthias Englert, Heiko Röglin, Jacob Spönemann, and Berthold Vöcking. Economical Caching. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 385-396, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{englert_et_al:LIPIcs.STACS.2009.1826,
  author =	{Englert, Matthias and R\"{o}glin, Heiko and Sp\"{o}nemann, Jacob and V\"{o}cking, Berthold},
  title =	{{Economical Caching}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{385--396},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1826},
  URN =		{urn:nbn:de:0030-drops-18263},
  doi =		{10.4230/LIPIcs.STACS.2009.1826},
  annote =	{Keywords: Online algorithms, Competitive analysis, Storage management}
}
Document
DOI: 10.4230/DagSemProc.07391.1
07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms

Authors: Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, and Berthold Vöcking

Published in: Dagstuhl Seminar Proceedings, Volume 7391, Probabilistic Methods in the Design and Analysis of Algorithms (2007)

Abstract
From 23.09.2007 to 28.09.2007, the Dagstuhl Seminar 07391 "Probabilistic Methods in the Design and Analysis of Algorithms''was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. The seminar brought together leading researchers in probabilistic methods to strengthen and foster collaborations among various areas of Theoretical Computer Science. The interaction between researchers using randomization in algorithm design and researchers studying known algorithms and heuristics in probabilistic models enhanced the research of both groups in developing new complexity frameworks and in obtaining new algorithmic results. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Martin Dietzfelbinger, Shang-Hua Teng, Eli Upfal, and Berthold Vöcking. 07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms. In Probabilistic Methods in the Design and Analysis of Algorithms. Dagstuhl Seminar Proceedings, Volume 7391, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{dietzfelbinger_et_al:DagSemProc.07391.1,
  author =	{Dietzfelbinger, Martin and Teng, Shang-Hua and Upfal, Eli and V\"{o}cking, Berthold},
  title =	{{07391 Abstracts Collection – Probabilistic Methods in the Design and Analysis of Algorithms}},
  booktitle =	{Probabilistic Methods in the Design and Analysis of Algorithms},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7391},
  editor =	{Martin Dietzfelbinger and Shang-Hua Teng and Eli Upfal and Berthold V\"{o}cking},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07391.1},
  URN =		{urn:nbn:de:0030-drops-12915},
  doi =		{10.4230/DagSemProc.07391.1},
  annote =	{Keywords: Algorithms, Randomization, Probabilistic analysis, Complexity}
}
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