Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension

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