Approximation ineffectiveness of a tour-untangling heuristic

DOI10.1007/978-3-031-49815-2_1MaRDI QIDQ6574920

Jesse van Rhijn, Bodo Manthey

Publication date: 19 July 2024

zbMATH Keywords

local searchprobabilistic analysistravelling salesperson problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• The Euclidean traveling salesman problem is NP-complete
• Flip distance to some plane configurations
• Smoothed analysis of algorithms
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• Smoothed Analysis of the 2-Opt Algorithm for the General TSP
• Combinatorial optimization. Theory and algorithms
• On the longest flip sequence to untangle segments in the plane
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem

This page was built for publication: Approximation ineffectiveness of a tour-untangling heuristic