0
$\begingroup$

Lets say I have a finite set of items like the following:

{$a_1, a_2, ... , a_n$}

And I have a finite list of sets of these items. For example:

[{$a_1$}, {$a_1, a_2$}, {$a_1, a_2, a_3$}, {$a_1, a_3$}, {$a_2$}, {$a_2$}, {$a_2$}, {$a_3$}]

I then take one item from each set. For example, in the above case, I could do:

$a_1$ <- {$a_1$}
$a_2$ <- {$a_1, a_2$}
$a_1$ <- {$a_1, a_3$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1$ <- {$a_1, a_2, a_3$}
$a_3$ <- {$a_3$}

In this case, the totals are:

$a_1$: 3
$a_2$: 4
$a_3$: 1

And the minimum is 1.

But lets say I want to maximise the minimum. I could instead select the items like:

$a_1$ <- {$a_1$}
$a_2$ <- {$a_1, a_2$}
$a_3$ <- {$a_1, a_3$} (changed)
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1$ <- {$a_1, a_2, a_3$}
$a_3$ <- {$a_3$}

And the totals are:

$a_1$: 2
$a_2$: 4
$a_3$: 2

And the minimum is 2.

Lets say also I allow the items to be assigned in a weighted way. Like the following:

$a_1$ <- {$a_1$}
$a_1$ <- {$a_1, a_2$} (changed)
$a_3$ <- {$a_1, a_3$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1: 0.5, a_3: 0.5$ <- {$a_1, a_2, a_3$} (changed)
$a_3$ <- {$a_3$}

And the totals are:

$a_1$: 2.5
$a_2$: 3
$a_3$: 2.5

And the minimum is 2.5.

We can't evenly assign the items in these sets because three of them only contain {$a_2$}.

So what's a fast algorithm for doing the above, i.e. finding the maximum "minimum"? I need something exact, not an approximation.

$\endgroup$
2
$\begingroup$

This can be solved by standard linear programming algorithms. A set of weighted choices is described by variables $y_{ij}$, where $y_{ij}=w$ if we choose $a_i$ from the $j$th set with weight $w$. To set this up, we use an additional variable $m$ which will represent the minimum number of times any variable is selected. We then have four kinds of constraints:

  • for each $i$, $j$: $0 \le y_{ij} \le 1$ if $a_i$ is in the $j$th set;
  • for each $i$, $j$: $y_{ij} = 0$ if $a_i$ is not in the $j$th set;
  • for each $j$: $\sum_i y_{ij}=1$ [choosing a total of 1 element from the $j$th set];
  • for each $i$: $m \le \sum_j y_{ij}$ [$m$ is at most the number of chosen $a_i$'s].

We choose the $y_{ij}$'s to maximize $m$; the constraints and the objective function are linear. (In the non-weighted case, we additionally require $y_{ij}$ to be integral; this makes the problem harder but integer linear programming packages are readily available.)

This formulation has the following geometric interpretation. Identify $a_i$ with the $i$-th standard basis vector in $\mathbf{R}^n$. For each set, say $\{a_{i_0},\ldots,a_{i_k}\}$, the collection of possible weighted choices from this set is the $k$-simplex with the given $a_{i_j}$'s as vertices. The Minkowski sum of all these simplices is the convex polyhedron which contains precisely the possible vectors $(x_1,\ldots,x_n)$ of totals for the elements $a_1,\ldots,a_n$. The linear programming formulation above seeks a point in this polyhedron which is as far from as possible from the nearest coordinate hyperplane.

$\endgroup$
2
  • $\begingroup$ I think I get this, but could you go into further detail about how how I can use my evaluation function? Isn't it non-linear? $\endgroup$
    – Clinton
    Jul 4 '13 at 8:09
  • $\begingroup$ For each a_i, the number of occurrences of a_i is linear in the y_ij's. You're trying to maximize the min of these, which as you say is nonlinear, but it's not too bad -- it's the min of a finite number of linear functions. So you introduce the auxiliary variable m, and impose the (linear) constraints that m is at most the number of occurrences of each of the a_i's. When you maximize m, m is forced to be the min you were looking for. $\endgroup$
    – Tad
    Jul 5 '13 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.