There are some $n$ people and $2 n$ items. Each person assigns a positive value to each item. The items should be allocated to the people, giving exactly 2 items to each person. The value of a person is the sum of values of the two allocated items. The goal is to maximize the minimum value of a person. For example, suppose $n=2$ and the values are:

  • Alice: w=1, x=2, y=3, z=4
  • Bob: w=5, x=6, y=7, z=8

Then the max-min partition is giving y,z to Alice and w,x to Bob, as the minimum value is 3+4=7, and this is the largest possible minimum value.

If there is only 1 item per person, then the problem can be solved in polynomial time by reduction to maximum matching.

In contrast, if there are 3 items per person, then the problem is NP-hard, by reduction from the 3-partition problem.

The case of 2 items per person is in between, so I do not know: is it NP-hard? Or is it solvable in polynomial time?


1 Answer 1


The case of 2 items per person is also NP-hard, also by reduction from the 3-partition problem.

Consider the case where each person $i \in [n]$ has a "value score" $v_i$, each item $j$ has a "value score" $w_j \in [2n]$, and the value person $i$ has for items $j$ is $v_i/2 + w_j$. In particular, the total value person $i$ has for the pair of items $(j, k)$ is $v_i + w_j + w_k$, and in any assignment of pairs of items to people, the total value among all people will be exactly $V = \sum_{i \in [n]} v_i + \sum_{j \in [2n]} w_j$.

Now, the maximal possible minimal value is at most $V/n$. It will equal $V/n$ iff the 3-partition problem with the set of weights $\{v_i\} \cup \{w_j\}$ is solvable (technically, this is a slight variant of the 3-partition problem where you must choose one element from the first set and two elements from the second set, but you can easily reduce this to the original 3-partition problem by simply adding a large constant $C$ to all $v_i$). Since you can embed any 3-partition problem in this way, the original problem is also NP-hard.

  • $\begingroup$ I think the reduction in parentheses goes in the wrong direction. You need to reduce 3partition to the slight variant. $\endgroup$ Commented Feb 1 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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