algorithm - 这有多项式算法吗？可能是动态规划方法？

Question

假设给定一个集合 A = {1, 2, ..., m} 和一个集合 B = {1 , 2, ..., n}，这样集合A中的每个元素都必须分配给B中的某个元素>。集合 A 中的每个元素 i 和集合 B 中的每个元素 j 的以下参数是已知的:

• S_ij 是将元素 i 分配给元素 j 大于或等于零的成本；
• t_ij 是元素 i 对元素 j 大于或等于零的最小偏好；
• T_ij 是元素 i 对元素 j 大于或等于零的最大偏好。

对于每个固定的i，t_ij、T_ij的所有值>(对于所有 j)是不同的。 m和n为大于0的整数，其他变量为非负实数。

A 中的元素根据它们的偏好t_ij(或T_ij)。例如，如果 t_ij <t_ik(首选项 T_ij 或 T_ik 可以在任何情况下使用，进一步阅读)，然后元素 i 将被分配给 j 而不是 k。在 mn 个偏好中，恰好有 r 个必须使用 T_ij 的值作为偏好值，剩下的 mn - r 必须使用 t_ij 的值(比 T_ij)。

如果将元素 i 分配给元素 j，则将成本 S_ij 添加到分配给元素 j 的总成本，即 C_j = C_j + S_ij。设Max是所有成本C_j中的最大值，Min是所有成本C<中的最小值sub>j。目标是选择分配元素 i 到元素 j 的哪些偏好将取 T_ij 的值，以及哪些首选项将采用 t_ij 的值，这样的值:

1. Max 是最小的；
2. Max - Min 是最小值。

我认为有一些动态规划算法，但我不确定。有谁知道如何通过 DP 方法或任何其他方法解决这个问题？然而，它可能不是多项式，但我认为它是。

示例。令m = 3，n = 2，即A = {1, 2, 3} 和 B = {1, 2, 3}。设 r = 2，矩阵 S、t 和 T 为

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

在最小化 Max 值的情况下，解等于 5。可以构建类似的示例来最小化 Max - Min。

Answer 1

问题是 NP-hard，可以通过减少 Partition 来证明。给它。

假设我们有一个算法 M 可以最优地解决您的问题。

我们得到一个分区实例 X = {x₁, x₂, ..., x _m} 并希望找到将 S 划分为具有最小和差的两个子集。让我们定义 n = 2, S_ij = x_i, t_ij = -j, T_ij> = j。现在我们只是迭代所有可能的 r 并将 M 作为子例程调用以找到 Max 的全局最小值。我们可以证明导致最小 Max 的分配是 X 的最佳 2 分区。

由于您使用的不是整数成本而是实际成本，并且您的问题对于 n > 2 可能会变得更难(我们还可以将 Bin packing 减少为 n 以直接的方式解决您的问题)，除非 P = NP，否则您的问题似乎不太可能存在伪多项式解。您应该考虑使用启发式方法来获得良好的近似解。一个好的起点是查看 Bin packing 的近似方案，并尝试使它们适应您的问题。也许一个简单的首次适应方法就足以满足您的需求。还有两件事你应该记住:

• 您可以对 Max 进行二进制搜索，然后将其用作“bins”的固定上限
• t_ij 和 T_ij 对于固定的 i 可以减少到它们各自的 argmins 。您有一组偏好 T_i,1(从 t_ij 中提取)和一组替代偏好对于每个 i，T_i,2(从 T_ij 中提取)。即使考虑非最低限度的偏好也没有意义。