Here is the algorithmic problem I'm trying to solve:

Given a list of integers $x_1, x_2, \dots, x_n$ find a permutation $p_1, p_2, \dots, p_n \in [n]$ that maximises the sum $\sum_{i=1}^{n-1}|x_{p_{i+1}} - x_{p_i}|$.

I think this can be solved in $O(n\log n)$, I thought of sorting the list and returning a list where first element is maximum element, next element is minimum, next is maximum of those which are left, etc. But this leads to nowhere, I cannot prove that it's correct, so probably it isn't. So, any tips how to tackle this problem?

  • 3
    What is $|\cdot|$ of a list? Do you mean: Given a list of integers $x_1, x_2, \dots, x_n$, find a permutation $p_1, p_2, \dots, p_n \in [n]$ that maximizes $\sum_{i=1}^{n-1} |x_{p_{i+1}} - x_{p_i}|$? – Michael Blondin Dec 13 '14 at 2:00
  • 2
    Your idea sounds like a kind of greedy strategy. Try the exchange argument for its correctness proof. – hengxin Dec 13 '14 at 5:52
  • I don't understand the close votes here, and the comments and answers that seem to be responding to a different question, "prove that my greedy algorithm is correct". What the OP actually asked for is a different algorithm, assuming (accurately given hengxin's answer) that greedy is incorrect. It seems research-level and on-topic for this board. – David Eppstein Dec 13 '14 at 18:40
up vote 7 down vote accepted

This is not a complete answer, but it may be helpful.

A piece of Mathematica code finds a counterexample of your greedy strategy: Consider the list of integers $\{51,54,55,70,98\}$.

Your algorithm gives $\{98,51,70,54,55\}$ (Have I misunderstood your idea?) and the sum is 83.

The program produces four permutations with the sum 125: $\{54, 98, 51, 70, 55\}, \{54, 70, 51, 98, 55\}, \{55, 98, 51, 70, 54\}, \{55, 70, 51, 98, 54\}$.

It seems that you should put the maximal(s) between minimal(s) as far as possible.

You can post other greedy strategies and prove (or disprove!) them by employing (maybe combining them) classic proof strategies such as mathematical induction, contradiction, and exchange argument.


Edit:

Actually, I don't quite understand why my answer (instead of that of @Marzio De Biasi) was accepted. Maybe the OP only want to know whether his/her greedy strategy is correct or not. Whatever, please refer to the answer of @Marzio De Biasi (and also other ones) for a complete solution.

  • 1
    To me this answer makes the OP's question more interesting, because it makes it clear that some more sophisticated idea will likely be needed to solve the problem. – David Eppstein Dec 13 '14 at 18:19

I found that the problem has been used in a student programming contest.

... if you still want to try to solve it by yourself don't move the mouse over the area below !!! :-)

The programmingn contest is the Bubble Cup 7DC, Belgrade 2012.

The key idea to solve it is to consider the middle element of the given array after sorting it in increasing order (if the number of elements is even then pick the value between the two middle elements); it splits the set in two halves $A$ and $B$.

Then it is easy to prove that an optimal solution cannot contain three consecutive elements in increasing (or decreasing) order $... x_i < x_j < x_k ...$ because it is enough to move the middle element at the end of the array and the sum cannot decrease after the trasformation. So an optimal solution must proceed in a zig-zag style. Then we can prove that the optimal solution cannot contain two consecutive elements from the same side. Suppose that we have somewhere $... x_i, x_j, x_k ...$ with $x_i> x_j < x_k$ and $x_i, x_j, x_k \in B$. Then then the remaining sequence must contain three consecutive elements from $A$ $...x'_i,x'_j,x'_k...$ ordered as $x'_i < x'_j > x'_k$. Then $A \ni x'_j < x_j \in B$ can be swapped preserving the inequalities and strictly increasing the value of the sum.

For the detailed proof see: Bubble Cup 7DC - Problem C: MaxDiff

(it contains other nice problems)

  • 2
    A "joke" solution occurs to me: once you notice the obvious zig-zag property, this becomes a linear optimizition over the permutohedron of $x$ and can be solved with linear programming. Not the kind of thing that gets you far in a programming contest though :) (or in the real world for that matter). – Sasho Nikolov Dec 13 '14 at 21:08
  • @SashoNikolov: it could be another answer :-) However in the spirit of the contest I "protected" the solution with a spoiler. – Marzio De Biasi Dec 13 '14 at 21:14
  • Can you explain what is meant by "it is enough to move the middle element at the end of the array"? I had a hard time parsing that sentence. Do you mean moving $x_j$ somewhere? where? swapping $x_j$ with $x_k$? – D.W. Dec 13 '14 at 23:36
  • 1
    @D.W.: suppose that in the optimal solution there are 3 consecutives increasing elements: $x_a, .... , x_i < x_j < x_k, ...., x_b$ then the contribution to the total sum is $(x_k - x_j) + (x_j - x_i)$ if we remove $x_j$ the total sum doesn't change, so we can move $x_j$ at the end (or at the beginning) of the sequence and get an increment of $max( |x_a - x_j|, |x_b - x_j|) \geq 0$. – Marzio De Biasi Dec 14 '14 at 0:56

Although I'm late to the game, it's still useful to have a reference.

This is a variation of the dart board design problem. The $x_i$s are the scores for each wedge of the dart board. The goal is to make sure if one decide to hit a particular slice, there will be a huge penalty if the player misses: A large gap in the scores between two adjacent wedge. Hence it is formulated as maximize $$\sum_{i=1}^n |x_{\pi(i)}-x_{\pi(i-1)}|^p$$

where $p\geq 1$ and $\pi$ is a permutation and $\pi(0)=\pi(n)$. Your version that maximize $$\sum_{i=2}^n |x_{\pi(i)}-x_{\pi(i-1)}|^p$$ is the hoopla board design problem.

Curtis have a greedy algorithm for both problems, and it is very close to your algorithm$^1$. The only difference is you are growing the list in only one direction, but Curtis grow the list in both direction: add an element that maximizes the difference to either end of the list.

Update :

Actually, this follows directly from an much older result that keep getting rediscovered: (maximum) TSP problem where the distance matrix is a Supnick matrix.

  1. S.A. Curtis, Darts and hoopla board design, Information Processing Letters, Volume 92, Issue 1, 16 October 2004, Pages 53-56, ISSN 0020-0190, http://dx.doi.org/10.1016/j.ipl.2004.06.005.
  • Now this problem is not only interesting, but also practical and meaningful, which make it even more interesting. – hengxin Dec 14 '14 at 1:53

The starting point with evaluating any greedy algorithm is to try running it on a bunch of examples, to see if it always works on all of them. (Hint: write a program, generate one million test cases, and see if it computes the right answer for every one of them.)

If it fails on any of them, you have a counterexample, and you know your algorithm is incorrect.

If it works on all of them, then you can start looking for a proof of correctness. Typically this will involve a kind of "swapping" or "exchange argument". See any good textbook in the section on greedy algorithms; it will typically present examples of greedy algorithms and proofs that use this strategy.

  • 2
    A piece of code finds a counterexample of the greedy strategy of the OP: ${51,54,55,70,98}$. $\{54,98,51,70,55\}$ gives the sum 125, which is bigger than that given by $\{98,51,70,54,55\}$. – hengxin Dec 13 '14 at 13:56

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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