[Solved]: Greedy algorithm correctness proof for “Elegant Permuted Sum” (UVa 11158)

ignougroup
Problem Detail: 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…

Asked By : matheuscscp

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43874  Ask a Question  Download Related Notes/Documents