Euclidean travelling salesman problem with location-dependent and power-weighted edges

DOI10.1007/S10959-021-01080-XMaRDI QIDQ2135191zbMATHOpenAlexWikidataFDO

Authors Ghurumuruhan Ganesan

Publication date 4 May 2022

Published in Journal of Theoretical Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.10716

zbMATH Keywords

travelling salesman problemdeviation estimateslocation-dependent edge weights

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05)

Abstract: Consider~(n) nodes~({X_i}_{1 leq i leq n}) independently distributed in the unit square~(S,) each according to a distribution~(f) and let~(K_n) be the complete graph formed by joining each pair of nodes by a straight line segment. For every edge~(e) in~(K_n) we associate a weight~(w(e)) that may depend on the emph{individual locations} of the endvertices of~(e) and is not necessarily a power of the Euclidean length of~(e.) Denoting~(TSP_n) to be the minimum weight of a spanning cycle of~(K_n) corresponding to the travelling salesman problem (TSP) and assuming an equivalence condition on the weight function~(w(.),) we prove that~(TSP_n) appropriately scaled and centred converges to zero a.s. and in mean as~(n ightarrow infty.) We also obtain upper and lower bound deviation estimates for~(TSP_n.)

Recommendations

• Traveling salesman problem across well-connected cities and with location-dependent edge lengths
• The traveling salesman problem under squared Euclidean distances
• APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
• Asymptotics for the Euclidean TSP with power weighted edges
• Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
• Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
• Location problems with costs being sums of powers of Euclidean distances
• Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
• Hard to solve instances of the Euclidean traveling salesman problem

Cites work

• scientific article; zbMATH DE number 6297797 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• New Bounds for the Traveling Salesman Constant
• On the Fluctuations of the Stochastic Traveling Salesperson Problem
• Probability theory of classical Euclidean optimization problems
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• The traveling salesman problem and its variations.

Cited in

(3)

• Asymptotics for the Euclidean TSP with power weighted edges
• Traveling salesman problem across well-connected cities and with location-dependent edge lengths
• Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation

This page was built for publication: Euclidean travelling salesman problem with location-dependent and power-weighted edges

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