4
$\begingroup$

Given a sequence of $2 \leq n \leq 50$ numbers $s = (s_1,s_2,...,s_n)$, find a permutation $a = (a_1,a_2,...,a_n)$ of $s$ such that $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$ is maximized.

I found many codes that get "Accepted" in the online judge with the following greedy algorithm.

If $n = 2$, then $a = s$. Stop the algorithm.

Let $s' = (s'_1,s'_2,...,s'_n)$ be $s$ in the non decreasing order. Start the optimal sequence with $a = (s'_1,s'_n)$ and remove these two elements from $s'$.

$\text{loop}$: Let $s' = (s'_1,s'_2,...,s'_k)$ be the remaining sorted sequence. If $k = 0$, stop the algorithm. If $k > 0$, from the following choices, choose the one that yields the greatest absolute difference.

  1. Remove $s'_1$ from $s'$ and push it to the front of $a$.
  2. Remove $s'_1$ from $s'$ and push it to the back of $a$.
  3. Remove $s'_k$ from $s'$ and push it to the front of $a$.
  4. Remove $s'_k$ from $s'$ and push it to the back of $a$.

Go to $\text{loop}$.

I'm having trouble to formally prove the correctness of this algorithm.

For example, to prove the optimal substructure property. Let $b = (b_1,b_2,...,b_n)$ be an optimal solution. How can I argue that $(b_1,b_2,...,b_{n-1})$ is also optimal? What if it's not???

And for proving the greedy-choice property. Let $a = (a_1,a_2,...,a_m)$ be a partial, yet still optimal, solution. The algorithm relies on the fact that only adding $s'_1$ or $s'_k$ to $a$ can yield another optimal solution. Why is this true? And more, why we don't need to test inner positions for inserting the new element, but only the ends?

Any help with these proofs? Or, perhaps, this algorithm is not correct? But I can't find a counterexample...

$\endgroup$
  • $\begingroup$ It is not necessarily the case that only adding $s'_1$ or $s'_k$ yields an optimal solution. Rather, there is always some choice of that type which yields an optimal solution. In order to prove the correctness of the algorithm, you prove by induction that at any point, there is an optimal solution extending $a$. $\endgroup$ – Yuval Filmus Jun 24 '15 at 1:32
  • 1
    $\begingroup$ How do you do this? By induction, there is some optimal solution extending $b$, which is the value of $a$ from the last round. Now you take any solution extending $b$, and show how to modify it so that it extends $a$ while not decreasing the objective function. That is the crux of the proof. $\endgroup$ – Yuval Filmus Jun 24 '15 at 1:33
  • $\begingroup$ Have you tried working through some small examples? Often that helps you understand what's going on and helps you formulate a proof strategy. $\endgroup$ – D.W. Jun 24 '15 at 2:17
  • $\begingroup$ @YuvalFilmus Thanks for helping! But, by $a$, you mean the partial solution of the algorithm, right? And $b$ is just any optimal solution. In this case, I don't get what you mean by "there is some optimal solution extending $b$, which is the value of $a$ from the last round". Actually, I don't understand any relation between $a$ and $b$, because $b$ is not necessarily the final result of $a$ (the partial solution), it's just any hypothetical optimal solution to the problem. Can you try again? Thanks! $\endgroup$ – matheuscscp Jun 24 '15 at 2:17
  • 2
    $\begingroup$ related post at cs.theory $\endgroup$ – hengxin Jun 24 '15 at 3:08
2
$\begingroup$

This algorithm appears and is analyzed in Curtis, Darts and hoopla board design. Curtis actually considers two problems:

  1. Dartboard design: Given a sequence of numbers, find a circular arrangement $a_1,\ldots,a_n$ maximizing $\sum_{i=1}^n |a_i-a_{i+1}|^q$ for some $q \geq 1$ (where $a_{n+1} = a_1$).

  2. Hoopla board design: Given a sequence of numbers, find a permutation $a_1,\ldots,a_n$ maximizing $\sum_{i=1}^{n-1} |a_i-a_{i+1}|^q$ for some $q \geq 1$.

Your problem is the hoopla board design with $q = 1$. You can find a complete proof of the greedy algorithm in Curtis' paper. It's not trivial, though also not too complicated.

$\endgroup$
  • $\begingroup$ Well, trivial for some people, hahaha... Thanks! $\endgroup$ – matheuscscp Jun 24 '15 at 6:43
  • $\begingroup$ @matheuscscp Sorry, that was a typo. I did mean not trivial. It takes a few pages of the article. $\endgroup$ – Yuval Filmus Jun 24 '15 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.