# Optimization over permutation

## The Problem

This is the problem I am working on: Given a set $$X = \{x_1, x_2, \cdots , x_n\}$$ in a metric space, find an optimal ordering $$\pi : X \rightarrow X$$ that maximizes the following objective function: \begin{equation*} \begin{aligned} \max_{\pi} \quad D(\pi ) = & \sum_{i=1}^n \sum_{j = 1}^{i-1} p^i d(x_{\pi(i)}, x_{\pi(j)}). \end{aligned} \end{equation*}

where $$d(\cdot, \cdot)$$ is metric distance, and $$0 < p < 1$$.

In the following, $$d(x, X) = \sum_{u \in X} d(x, u)$$.

## General Question:

This optimization problem seems like one that should be well known. I feel that if I knew the name of it I would have been able to search it on my own.

## My Thoughts

1. Hardness: This problem is likely to be NP-complete, and it should be supermodular wrt X.

2. My Specific Question:

I want to first find some property of the optimal ordering. Specifically, I hope I can prove this assumption: In the optimal ordering, $$d(x_{\pi(n)},X) \leq \sum_{i \in [n]} \frac{d(x_{\pi(i)}, X)}{n} = \text{avg}_i d(x_i, X)$$ always holds. i.e., the last item in the ordering has a smaller distance to $$X$$ than the average distance of any item to $$X$$.

I tried to proof this assumption by contradiction: Assume $$d(x_{\pi(n)},X) > \text{avg}_i d(x_i, X)$$, then there must be an index $$k$$ such that $$d(x_{\pi(k)},X) < \text{avg}_i d(x_i, X)$$. By swapping $$x_{\pi(n)}$$ with $$x_{\pi(k)}$$ I get a new ordering $$\pi'$$, and I want to prove $$D(\pi') > D(\pi)$$ which will contradict $$\pi$$ is the optimal ordering.

However, I cannot prove $$D(\pi') > D(\pi)$$: I wrote down the equations step by step, but I cannot get the expected result. This is because I know nothing about the optimal ordering besides $$d(x_{\pi(n)},X) > \text{avg}_i d(x_i, X)$$ and $$d(x_{\pi(k)},X) < \text{avg}_i d(x_i, X)$$;

In fact, if I do not use any properties of "$$\pi$$ is optimal", then proving $$D(\pi') > D(\pi)$$ implies: for any ordering $$\pi_{r}$$ s.t. $$d(x_{\pi_r(n)},X) > \text{avg}_i d(x_i, X)$$ you can find a new ordering $$\pi_r^{'}$$ (by doing the swap stated above) and $$D(\pi_r) > D(\pi_r^{'})$$ always holds. This is of course not true.

So my specific question is, what am I missing in the proof by contradiction? I think I need to find more property of the optimal $$\pi$$ and use it in the proof. But I cannot find it now.

Sorry, I misread your objective function as $$\sum_{i=1}^{n-1} p^i d(x_{\pi(i)}, x_{\pi(i+1)}).$$
• thank you for your nice answer! I have a further question: In the time dependent tsp, we usually assume the cost C_{i,j,t} is a given value, right? Usually C_{i,j,t} can be expressed as a step function w.r.t t. However, if we reduce my problem to the TDTSP, then C_{i,j,t} will depend not only on $t$, but all other nodes that are visited before node $j$. Specifically, in permutation (dummy node, x_1, x_2, ... x_n, dummy node), C_{i,j,t}=d(x_j, {dummy node, x_1, ...x_i}) * p^{i+1} if t=i, and 0 therwise. In this case, I do not see an easy way of using TDTSP to solve my problem. Sep 15, 2023 at 8:58