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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Insertion Heuristics for (1,2)-TSP

  • Ekin Ergen

摘要

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.