33 citations · 38 across the 4 of their papers we have counts for
4 papers
Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
Matthias Englert, Heiko Röglin, Berthold Vöcking
2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on real world Euclidean instances both with respect to running t…
Primal Beats Dual on Online Packing LPs in the Random-Order Model
Thomas Kesselheim, Klaus Radke, Andreas Tönnis +1
We study packing LPs in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated,…
Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
Oliver Göbel, Martin Hoefer, Thomas Kesselheim +2
We investigate online algorithms for maximum (weight) independent set on graph classes with bounded inductive independence number like, e.g., interval and disk graphs with applicat…
Approximation Algorithms for Secondary Spectrum Auctions
Martin Hoefer, Thomas Kesselheim, Berthold Vöcking
We study combinatorial auctions for the secondary spectrum market. In this market, short-term licenses shall be given to wireless nodes for communication in their local neighborhoo…