Is there polynomial algorithm to this? Possibly dynamic programming approach?

Question

Assume you are given a set A = {1, 2, ..., m} and a set B = {1, 2, ..., n}, such that each element from the set A has to be assigned to some element from B. The following parameters for each element i from the set A and each element j from the set B are known:

• S_ij is the cost of assignment an element i to element j greater or equal to zero;
• t_ij is the minimal preference of element i to element j greater or equal to zero;
• T_ij is the maximal preference of element i to element j greater or equal to zero.

For each fixed i, all values of t_ij, T_ij (for all j's) are different. m and n are integers greater than 0, and the other variables are non-negative real numbers.

Elements from the set A are assigned to elements from B according to their preferences t_ij (or T_ij). For example, if t_ij < t_ik (preferences T_ij or T_ik might be used in any case instead, read further), then element i will be assigned to j rather then k. Out of mn preferences, exactly r of them have to use value of T_ij as a value of preference, and remaining mn - r have to use value of t_ij (which is lower value then T_ij).

If element i is assigned to an element j, then the cost S_ij is added to the total cost of assignment to element j, i.e., C_j = C_j + S_ij. Let Max be the maximum among all costs C_j and Min the minimum among all costs C_j. The goal is to choose which preferences of assignment element i to element j will take the value of T_ij, and which preferences will take the value of t_ij, such that the value of:

1. Max is minimal;
2. Max - Min is minimal.

I think there is some dynamic programming algorithm, but I'm not sure. Does anybody know how to solve this by DP approach, or any other? It might not be polynomial, however, but I think it is.

Example. Let m = 3, n = 2, i.e. A = {1, 2, 3} and B = {1, 2, 3}. Let r = 2, and matrices S, t and T be given as

    |5 9|      |1 3|      |10  7|
S = |7 1|, t = |4 2|, T = | 5  4|.
    |8 4|      |3 4|      | 9 12|

Solution is equal to 5 in the case of minimizing the value of Max. Similar example might be constructed for minimizing Max - Min.

Answer 1

The problem is NP-hard, which can be shown by reducing Partition to it.

Let's assume we have an algorithm M that solves your problem optimally.

We are given a Partition instance X = {x₁, x₂, ..., x_m} and want to find a partition of S into two subsets with minimum sum difference. Let's define n = 2, S_ij = x_i, t_ij = -j, T_ij = j. Now we just iterate over all possible r and call M as a subroutine to find the global minimum for Max. We can show that the assignment that results in the minimum Max is an optimal 2-partition of X.

Since you're not working with integer costs but with real costs and since your problem is likely to get harder for n > 2 (we can also reduce Bin packing with n bins to your problem in a straight-forward way), it seems highly unlikely that there exists even a pseudopolyonomial solution for your problem unless P = NP. You should consider using heuristics to get a good approximative solution. A good starting point would be to look at the approximation schemes for Bin packing and try to adapt them to your problem. Maybe a simple first-fit approach is enough for your needs. Two more things you should keep in mind:

• You can binary search for Max and then use it as a fixed upper bound for your "bins"
• t_ij and T_ij can be reduced to their respective argmins for a fixed i. You have a set of preferences T_i,1 (extracted from t_ij) and an alternative set of preferences T_i,2 (extracted from T_ij) for every i. No point even considering the non-minimal preferences.