Insertion Heuristics for (1,2)-TSP
摘要
Insertion heuristics are approximation algorithms that are widely used in practice to solve the traveling salesperson problem (TSP) which is arguably among the most prominent problems in combinatorial optimization. In this paper, we analyze well-known variants of insertion heuristics restricted to instances with edge weights in \(\{1,2\}\) , deriving the exact approximation ratio of 7/4 for multiple variants. These ratios yield the first tight bounds known for arbitrary insertion heuristic and the farthest insertion heuristic for any class on which TSP is NP-complete.