We consider a set of Euclidean optimization problems in one dimension, where the cost function associated to the couple of points $x$ and $y$ is the Euclidean distance between them… Click to show full abstract
We consider a set of Euclidean optimization problems in one dimension, where the cost function associated to the couple of points $x$ and $y$ is the Euclidean distance between them to an arbitrary power $p\ge1$, and the points are chosen at random with flat measure. We derive the exact average cost for the random assignment problem, for any number of points, by using Selberg's integrals. Some variants of these integrals allows to derive also the exact average cost for the bipartite travelling salesman problem.
               
Click one of the above tabs to view related content.