patternMinor
Max-min one-to-two matching
Viewed 0 times
minonemaxtwomatching
Problem
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:
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?
- 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?
Solution
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.
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.
Context
StackExchange Computer Science Q#164580, answer score: 3
Revisions (0)
No revisions yet.