An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
提出了非对称旅行商问题的首个突破对数近似比的随机算法，通过薄树概念和最大熵舍入方法实现，对运筹学和理论计算机科学研究者有价值。
We present a randomized O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem (ATSP). This provides the first asymptotic improvement over the long-standing Θ(log n)-approximation bound stemming from the work of Frieze et al. (1982) [Frieze AM, Galbiati G, Maffioki F (1982) On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks 12(1):23–39]. The key ingredient of our approach is a new connection between the approximability of the ATSP and the notion of so-called thin trees. To exploit this connection, we employ maximum entropy rounding—a novel method of randomized rounding of LP relaxations of optimization problems. We believe that this method might be of independent interest.