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

DOI10.1007/S10959-021-01080-XzbMATH Open1487.60019arXiv2011.10716OpenAlexW3134871540WikidataQ114225099 ScholiaQ114225099MaRDI QIDQ2135191FDOQ2135191

Authors: Ghurumuruhan Ganesan 

Publication date: 4 May 2022

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

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.)

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

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

zbMATH Keywords

travelling salesman problemdeviation estimateslocation-dependent edge weights

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05)

Cites Work

• Probability theory of classical Euclidean optimization problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The traveling salesman problem and its variations.
• Title not available (Why is that?)
• Subadditive Euclidean functionals and nonlinear growth in geometric probability
• New Bounds for the Traveling Salesman Constant
• On the Fluctuations of the Stochastic Traveling Salesperson Problem

Cited In (3)

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

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)