Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Berthold Vöcking:

TR10-052 | 8th March 2010
Melanie Winkler, Berthold Vöcking, Sascha Geulen

Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm

Suppose a decision maker has to purchase a commodity over time with
varying prices and demands. In particular, the price per unit might
depend on the amount purchased and this price function might vary from
step to step. The decision maker has a buffer of bounded size for
storing units ... more >>>

TR10-016 | 22nd December 2009
Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking

Online Capacity Maximization in Wireless Networks

In this paper we study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension $d$ arrive iteratively over time. When a new request arrives, an online algorithm needs to decide ... more >>>

TR06-092 | 5th July 2006
Matthias Englert, Heiko Röglin, Berthold Vöcking

Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

2-Opt is probably the most basic and widely used local search
heuristic for the TSP. This heuristic achieves amazingly good
results on "real world" Euclidean instances both with respect to
running time and approximation ratio. There are numerous
experimental studies on the performance of 2-Opt. However, the
theoretical knowledge about ... more >>>

TR06-067 | 12th April 2006
Heiner Ackermann, Heiko Röglin, Berthold Vöcking

On the Impact of Combinatorial Structure on Congestion Games

We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show, if the strategy space ... more >>>

ISSN 1433-8092 | Imprint