Re: Need help for subset problem

In article <1137122056.107559.207970@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<achilles75@xxxxxxxxx> wrote:
>Given N sets as A1, A2,..., An, find a subset Bi for each Ai, i = 1,
>2,..., n, subject to that for each i != j, the intersection of Bi and
>Bj is empty. The target is to maiximize the size of the subset Bk that
>has minimal number of elements among all the subset Bi, that is: max
>min{|Bi|, i = 1, 2,..., n}.
>What kind problem cat this problem categorized to? Any one can give me
>some ideas about how to solve this problem?

Let S = union {A_i: i=1..n}. Consider the linear programming problem
with variables m and x_{ij} for i in S, j={1,2,...,n}.

maximize m
subject to
sum_{j: i in A_j} x_{ij} <= 1 for each i in S
sum_{i in A_j} x_{ij} >= m for each j in {1,2,...,n}
all variables >= 0

If nonnegative integer m is fixed, this can be considered as a
"transportation problem" which can be solved very efficiently,
and if it is feasible a solution is found where the variables
x_{ij} all have integer values (in this case 0 and 1). The
interpretation is that B_j = {i: x_{ij} = 1}. With m as a
variable it's not a transportation problem, and there
is no guarantee that the optimal solution has integer values.
But if m* is the value of m in this solution, we know (by convexity
of the solution set) that every point in the interval [0,m*] is
the value of m in some feasible solution. So if you fix
m = floor(m*) (i.e. the greatest integer <= m) and solve again
(with linear programming software, if more specialized software for
transportation problems is not conveniently available to you) you
should get an optimal solution for your problem.

Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada


.