Algorithm to approximate an optimal solution for an integer allocation pro­blem

Question

I have the following problem:

Given a set of sums of variables like { a + b, b + c, c + d, a + a + d, b }, find positive integer values for the variables such that all sums are distinct and the highest sum is as small as possible.

Is there an algorithm to find or approximate a solution to this kind of problems?

Answer 1

I have created a possible solution and an implementation in C#. Hope it is what you need. It would be nice if someone proves it is correct/incorrect but it works and results look correct. The details on theory are below. Its complexity is something about O(N!*M^3*Log2(N)) where N is number of variables and M is number of summands all sums.

BTW, for your example it gives this result:

c=3, a=2, d=2, b=1
{a+b=3; b+c=4; c+d=5; a+a+d=6; b=1}
max=6

UPDATE

Theory of the algorithm.

Assume the variables are ordered, e.g. a >= b >= c >= .... Lets say a set of sums is a Bag if all sums in it are distinct. All sums in a Bag can be divided into two groups: sums that do not contain variable a and sums that do contain. Lets call the first group as Head and the second as Tail. Note that both are Bags because they contain distinct sums. We can subtract a from each sum in Tail so that all sums remain distinct (i.e. the Tail is still a Bag). This way we get two bags both without variable a.

Similar way we exclude variable b from two Bags and get four Bags. This operation we repeat for each variable until we get sums with last variable (lets say it is d). The smallest value of d is 1.

After that we can return to the previous step and include variable c in sums from tails. Remember that we have many pairs Head-Tail and need to join them back. To do that we add c to each sum in each Tail so that sums from the Tail have to be distinct from the Head.

How to calculate c? The idea is to calculate its invalid values and then take the smallest value that is not invalid and also is equal or greater than d. Calculating invalid values is trivial, using condition HeadSum != TailSum + c => c != HeadSum - TailSum. For each combination of tail sum and head sum we get all invalid values.

Collapsing all pairs Head-Tail back and calculating each variable we get the solution for the case a >= b >= c >= d. Then we calculate a solution for each permutation of a >= b >= c >= d and find the smallest one.

PS It would be great if someone provide better solution because I think my algorithm is somewhat of approximation (but a good approximation) or even better to prove it. The worst thing is N! complexity because of permutations and I still have no idea how to get rid of it.