From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Finding maximal sums
Date: 31 Mar 1998 18:05:11 GMT

In article <352066ec.8409292@news.gmu.edu>, rrosenbe@gmu.edu (Bob Rosenberg) writes:
|> I was wondering if anyone here knew of an "elegant" algorithm for the
|> following: There are n sets of integers (not necessarily the same
|> amount in each set) with all the integers in each set being different
|> and <= m. (Integers in different sets may be equal.) Find the maximal
|> sum K1 +K2 + ... + Kn, where Ki is in set i and K1, K2, ..., Kn are
|> ALL DIFFERENT.
 
|> Clearly, sometimes there are no K1, K2, ..., Kn that are all different
|> (as when all n sets are identical and contain less than n integers).
|> Also, the problem is trivial when all the greatest members are
|> different. But otherwise, is there a neat way to find the greatest
|> sum?

Let W = {w_j: j = 1 .. N} be the union of the sets of integers.  You want to 
maximize sum_{i,j} w_j x_{i,j} subject to
sum_i x_{i,j} <= 1 for each j
sum_j x_{i,j} = 1 for each i
x_{i,j} >= 0
x_{i,j} = 0 unless w_j is in set number i.

This is a particular type of linear programming problem: a "transportation 
problem", and there are efficient polynomial-time algorithms for it.  Note 
that by the "Integrality Theorem", if the problem is feasible there is an
optimal solution where the variables x_{i,j} have integer values.  You then
choose w_j from set number i if x_{i,j} = 1.  

Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Z2