pipette
ENEnglish

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

Sergio Caracciolo, Carlo Vanoni

Preprint

En palabras de los autores

We study the random Euclidean Maximum Traveling Salesman Problem: finding a Hamiltonian cycle of maximal total cost through any set of 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 and asymptotic expansions with power-law edge costs.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.