2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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)}).$$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Honglian
    Sep 15, 2023 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.