33 citations · 65 across the 7 of their papers we have counts for
4 papers · 1 filter
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…
Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
Matthias Englert, Nicolaos Matsakis, Pavel Veselý
In the Shortest Superstring problem, we are given a set of strings and we are asking for a common superstring, which has the minimum number of characters. The Shortest Superstring…
Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis +1
We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output…
Vertex Sparsifiers: New Results from Old Techniques
Matthias Englert, Anupam Gupta, Robert Krauthgamer +3
Given a capacitated graph and a set of terminals , how should we produce a graph only on the terminals so that every (multicommodity) flow betwee…