PreprintarXiv licencearXiv
Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
Abstract
We study the random Euclidean Maximum Traveling Salesman Problem: finding a Hamiltonian cycle of maximal total cost through any set of N cities on a line, where each edge cost is a function of its Euclidean length. We characterize the maximizing cycles for convex increasing, concave increasing, and convex decreasing cost functions. For points sampled independently and uniformly from the unit interval, we derive explicit expressions for the average maximal cost for arbitrary N and asymptotic expansions with power-law edge costs.
Related
- Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
- Traveling Salesman Problem on Graphs with Proportional Independent Set
- On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem
- Collaborative Attention Ant Colony Optimization for Large-Scale Traveling Salesman Problems
- Optimal Service Commitments in Traveling Salesman Problems with Stochastic Demand
BibTeX
@misc{caracciolo2026exact,
title = {{Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension}},
author = {Sergio Caracciolo and Carlo Vanoni},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26536},
eprint = {2610.26536},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26536},
}
RIS
TY - UNPB
TI - Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
AU - Sergio Caracciolo
AU - Carlo Vanoni
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26536
UR - https://arxiv.org/abs/2610.26536
AB - We study the random Euclidean Maximum Traveling Salesman Problem: finding a Hamiltonian cycle of maximal total cost through any set of N cities on a line, where each edge cost is a function of its Euclidean length. We characterize the maximizing cycles for convex increasing, concave increasing, and convex decreasing cost functions. For points sampled independently and uniformly from the unit interval, we derive explicit expressions for the average maximal cost for arbitrary N and asymptotic expansions with power-law edge costs.
ER -