{'fraction_non_alphanumeric': 0.03577661431064572, 'fraction_numerical': 0.027923211169284468, 'mean_word_length': 4.822335025380711, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Jens Vygen New approximation algorithms for the TSP

The traveling salesman problem (TSP) is probably the best known combinatorial optimization problem. Although studied intensively for sixty years, the TSP continues to pose grand challenges. Cook’s [2012] recent book gives an excellent introduction. Since the TSP is NP-hard (Karp [1972]), it is natural to ask for approximation algorithms. How good solutions can we guarantee to find in polynomial time? Christofides [1976] devised a 3 2 -approximation algorithm for the Symmetric TSP: it always finds a solution that is at most 50% longer than optimum. Can we do better? Can we do similarly well for the Asymmetric TSP? These questions – still unsolved – belong to the most intriguing open problems in our field. Recently, there has been progress that makes us hope that we will learn more in the near future. In this survey we try to describe the state of the art, in particular the recent progress, mostly from 2010–2012. We use standard notation and some basic terminology and well-known results from combinatorial optimization; see Korte and Vygen [2012] or Schrijver [2003] if necessary.