Greedy algorithm to pair numbers that minimizes the maximum sum

Go To StackoverFlow.com

4

The input is a sequence of real numbers x1, x2, ..., x2n. We want to pair these numbers into n pairs. For the ith pair, (i = 1, 2, ..., n), let Si denote the sum of numbers in that pair. (For example if you pair x(2i−1) and x2i as the ith pair, Si = x(2i−1) + x2i). We want to pair these numbers so that Maxi[Si] is minimized. Design a greedy algorithm to solve this problem.


That's the question; my solution is to simply sort the numbers and pair the first-last elements and add-one/subtract-one index and repeat. The algorithm tries to optimize for each pair, so that makes it greedy. I'm just wondering if there's a linear time algorithm that will do this?

PS: This is not homework, but I understand this looks very much like it.

2012-04-04 01:20
by user183037
the answer was deleted just now, but i was posting this: here's a link for anyone that is interested in lower bound of comparison based sorting on arbitrary elements - cctan 2012-04-04 01:40
I don't know what happened there - the answer seems to have vanished along with my comment! Thanks for the link, I'm aware that comparison based sorting on arbitrary elements has a lower bound of nlgn. What I'm wondering is if there was a linear way to pair the two numbers such that their sum is minimum. I take it what you're trying to say is that there's no other way without sorting and sorting has a lower bound of nlgn - user183037 2012-04-04 02:01
Your solution is correct. Sort numbers and pair first and last iteratively. I can provide proof if you want - ElKamina 2012-04-04 05:52


1

No. There can't be a linear time algo to get this done for you. The input numbers can be in any order so you cant get the pairing done right away with min Maxi[Si]. Your current solution is simple and good.

Suggestions to improve on the running time:

You can create a Binary tree out of the input numbers (this takes O(nlog(n)) time). Do inorder traversal of the tree and create pairs from the (first+i, last-i) elements (i from 0 to n/2)

2012-04-04 03:45
by Tejas Patil
Thanks for confirming that - user183037 2012-04-04 16:04
How does the binary tree improve on running time? Why is it any different from using any of the sort methods that run in O(nlgn) - user183037 2012-04-04 23:00
If you use sorting algo of O(nlgn), then it will be of same order as binary tree - Tejas Patil 2012-04-05 02:12


1

If you want to be greedy and approximate, you could run a fixed size window over the data, once, and only pair numbers within the window - the one at the left end of the window with any other one in the window - mark the one not at the left end, so you don't re-use it, and advance the window, so the one at the left end is not re-used. This is greedy in the sense of being only locally optimal. If you know the list is uniformly random it could be close, and it is linear, since sorting a list of constant length k is constant time, relative to N. With other knowledge about the distribution of the list you could use a variant that is still O(N) and only approximate.

2012-04-04 01:51
by DRVic
I don't think approximation is okay from what the question says. So I guess sorting over N is the only way out - user183037 2012-04-04 02:02