Approximation ineffectiveness of a tour-untangling heuristic

DOI10.1007/978-3-031-49815-2_1MaRDI QIDQ6574920zbMATH OpenFDO

Authors Bodo Manthey, Jesse van Rhijn

Publication date 19 July 2024

Full work available at URL https://doi.org/10.1007/978-3-031-49815-2_1

zbMATH Keywords

local searchprobabilistic analysistravelling salesperson problem

Mathematics Subject Classification ID

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

Cites work

• Combinatorial optimization. Theory and algorithms
• Flip distance to some plane configurations
• scientific article; zbMATH DE number 3882232 (Why is no real title available?)
• scientific article; zbMATH DE number 2064410 (Why is no real title available?)
• New Results on the Old k-opt Algorithm for the Traveling Salesman Problem
• On the longest flip sequence to untangle segments in the plane
• Smoothed analysis of algorithms
• Smoothed analysis of the 2-Opt algorithm for the general TSP
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
• The Euclidean traveling salesman problem is NP-complete

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6574920)