Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space

DOI10.1134/S0081543808060072MaRDI QIDQ735647zbMATH OpenOpenAlexFDO

Authors Eh. Kh. Gimadi

Publication date 23 October 2009

Published in Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0081543808060072

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• Approximation algorithms for solving the 2-peripatetic salesman problem on a complete graph with edge weights 1 and 2
• scientific article; zbMATH DE number 4068645
• scientific article; zbMATH DE number 2102640
• scientific article; zbMATH DE number 6004865

Cited in

(16)

• Euclidean travelling salesman problem with location-dependent and power-weighted edges
• scientific article; zbMATH DE number 4068645 (Why is no real title available?)
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Approximability of the problem about a minimum-weight cycle cover of a graph
• On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
• A polynomial algorithm with asymptotic ratio \(2/3\) for the asymmetric maximization version of the \(m\)-PSP
• scientific article; zbMATH DE number 2102640 (Why is no real title available?)
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• A polynomial 3/5-approximate algorithm for the asymmetric maximization version of the 3-PSP
• Sums of Squares of Edge Lengths and Spacefilling Curve Heuristics for the Traveling Salesman Problem
• scientific article; zbMATH DE number 1985657 (Why is no real title available?)
• scientific article; zbMATH DE number 6007868 (Why is no real title available?)
• scientific article; zbMATH DE number 4073022 (Why is no real title available?)
• Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph
• Seeking global edges for traveling salesman problem in multi-start search

This page was built for publication: Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space

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