Optimization over permutation

Question

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.

Answer 1

By introducing a dummy depot node, you can think of this as a special case of the time-dependent traveling salesman problem. The dummy node is adjacent to all other nodes, with zero-cost links.

You might also search for discounted-reward TSP.

---

Sorry, I misread your objective function as $$\sum_{i=1}^{n-1} p^i d(x_{\pi(i)}, x_{\pi(i+1)}).$$