Research Talk: Efficient Variants of the 2-Opt Heuristic for the TSPThe 2-opt heuristic is a simple and popular local search heuristic for the Traveling Salesperson Problem (TSP). Albeit its performance in practice, it has exponential worst-case running-time. We consider two restrictions of the 2-opt heuristic that run in polynomial time in the worst case and analyze their approximation performance.Read more- Research Talk: Approximation Algorithms with PredictionsWe initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear time algorithms for, e.g., Vertex Cover, Steiner Tree, Min-Weight Perfect Matching, Knapsack, and Clique. Our algorithms produce optimal solutions when provided with perfect predictions and their approximation ratios smoothly degrade with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond reach without predictions in the given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem. We conclude with an empirical evaluation of our approach.Read more
