The simultaneous semi-random model for TSP

• 成果类型: Article
• 署名作者: Balkanski, Eric; Faenza, Yuri; Kubik, Mathieu
• 署名单位: Columbia University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02011-w
• 发表日期: 2024
• 页码: 305-332
• 关键词: traveling salesman; smoothed analysis; algorithm

摘要

Worst-case analysis is a performance measure that is often too pessimistic to indicate which algorithms we should use in practice. A classical example is in the context of the Euclidean Traveling Salesman Problem (TSP) in the plane, where local search performs very well in practice even though it only achieves an O ((log log n)/ (log n) ) worst case approximation ratio. In such cases, a natural alternative approach to worst-case analysis is to analyze the performance of algorithms in semi-random models. In this paper, we propose and investigate a novel semi-random model for the Euclidean TSP. In this model, called the simultaneous semi-random model, an instance over n points consists of the union of an adversarial instance over (1 - a)n points and a random instance over an points, for some a ? [0, 1]. As with smoothed analysis, the semi random model interpolates between distributional (random) analysis when a = 1 and worst-case analysis when a = 0. In contrast to smoothed analysis, this model trades off allowing some completely random points in order to have other points that exhibit a fully arbitrary structure. We show that with only an a = (log n)/(1) fraction of the points being random, local search achieves an O(log log n) approximation in the simultaneous semi-random model for Euclidean TSP in fixed dimensions. On the other hand, we show that at least a polynomial number of random points are required to obtain an asymptotic improvement in the approximation ratio of local search compared to its worst-case approximation, even in two dimensions.