I am stuck with an optimization problem in one of my projects which requires me to find a permutation $\Sigma = \{x_{\sigma_1}, x_{\sigma_2}, \ldots, x_{\sigma_N}\}$ of a sequence $\{x_1, x_2, \ldots, x_N\}$ such that the following cost function is minimized
$$L(\Sigma) = \underset{1\le i < N}{\max} f(x_{\sigma_i}, x_{\sigma_{i+1}})$$
where $f$ is a function such that $f(a,b)=f(b,a)$ and it is always positive.
What have I done - I have come up with a simple approach to solve this problem where I create a fully connected (every node is connected to every other node) graph with $x_{1:N}$ as the nodes and the weight of edge connecting $x_i$ and $x_j$ being $f(x_i,x_j)$. Now I need to find a path in the graph such that it includes all the nodes and has the smallest maximum edge weight.
I solve this problem by using a greedy algorithm, I add edges to the graph one by one in increasing order of weights till my graph has a cycle of length $N$. The permutation can now be recovered by removing the edge with maximum weight from this cycle.
I believe that this algorithm is quite inefficient as I have to check for cycles in the graph at every iteration. Is there a better way to approach this problem?
EDIT Please see the answer by Misha, who has pointed out a problem with the algorithm I described.
Your greedy algorithm will not always be correct. Suppose that at some point you have built the following partial graph (circled values are edge weights):
If the next edge you add is from $2$ to $4$ with weight, say, $10$, then you'll create the cycle $(2,1,3,4)$, and after removing its maximum weight edge you'll have the path $(2,1,3,4)$. This has maximum weight $f(1,3) = 2$.
But if you waited instead for the edge from $3$ to $4$ to appear (even if it has weight $11$, then you would have found the path $(1,2,3,4)$ with maximum weight $1$.
In general, this is known as the Bottleneck traveling salesman problem (Wikipedia link) and is known to be NP-hard; Wikipedia suggests some (really slow) approaches to solve it. That version of the problem asks for a cycle, not a path, with least maximum weight; the problems are equivalent, since you could just add an artificial node $x_{0}$ with weights $f(x_0, x_i) = 0$ for all $i$. A cycle with least maximum weight including $x_0$ becomes a path with least maximum weight when you remove it.