CODEWITHSUNDEEP
algorithmpartitioninggreedy
Robin Yu
Robin Yu

Reputation: 339

Maximizing the minimum difference between elements in a set

I recently thought of this problem, and I thought of an "instinctive" greedy solution but I can't prove its optimality.

You are given N integers, V1, V2, ..., VN and K sets (K < N).

You need to find a way of partitioning the integers into the sets, so that the minimum difference between any two elements in the same set is maximized.

For example, when the integers are 1, 5, 6, 8, 8 and you have 2 sets, an optimal way of partitioning the integers would be

{1, 6, 8}

{5, 8}

So the minimum difference is between 6 and 8, which is 2.

This arrangement is not unique, for example

{1, 5, 8}

{6, 8}

Also gives a minimum difference of 2.

I was thinking, if I can use a greedy algorithm to solve this.

I would sort it first, and then put all V1, V1+K, V1+2K... together, and then all V2, V2+K, V2+2K... together, and so on.

Is there a proof for the optimality of this solution, or a counterexample where this does not work?

Thanks.

Upvotes: 2

Views: 1056

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58211

Yes, it's optimal. We'll show that if a difference D appears using your process, then for any arrangement of the numbers there's a pair of numbers in the same set which differ by at most D.

To prove it, consider adding the sorted numbers one by one to the K sets. Let's call the sorted numbers x[i]. Suppose we're adding x[n] to one of the sets. The largest value in that set is x[n-k], with x[n]-x[n-k] = D for some D.

Now, the set x[n-k], x[n-k+1], ..., x[n] is a set of k+1 numbers, all of which differ from each other by at most D (for x[n]-x[n-k] = D).

By the pigeon-hole principle, two of these k+1 numbers must fall in the same set no matter how you arrange them, so the maximum minimum distance must be at most D.

This proves that if a distance D appears in your process, then the maximum minimum distance achievable is at most D.

Let D_min be the smallest difference between two numbers in the same set using your process. Then we've shown that the maximum minimum distance achievable is <= D_min, but also D_min <= maximum minimum distance (since D_min is a minimum distance) which shows that D_min is the maximum minimum distance.

Upvotes: 2

Related Questions