algorithm - 有谁知道这是否是多项式可解的？

Question

您好，我正在处理以下问题。

给定一个大小为 M x N 且系数为正的矩阵。目标是选择 P 列，使得所得 M x P 矩阵的每一行中所有元素的最大总和最小。例如，如果 M = 3、N = 5、P = 2 并且矩阵由

a₁₁ a₁₂ a₁₃ a₁₄ a₁₅
a₂₁ a₂₂ a₂₃ a₂₄ a₂₅
a₃₁ a₃₂ a₃₃`a₃₄ a₃₅

最佳解决方案是选择`第 2 列和第 4 列，结果矩阵由下式给出

a₁₂ a₁₄
一个₂₂一个₂₄
a₃₂ a₃₄

和最大值{a₁₂ + a₁₄, a₂₂ + a₂₄, a< sub>32 + a₃₄} 在所有 P 列选择中最小。

由于存在(N 超过 P)个解，可以实现一个简单的指数算法来解决这个问题，但是有没有更快的多项式时间解呢？

或者，如果没有，谁能肯定地证明这是一个 NP-hard 问题？您是否知道任何类似的 NP 难问题可以简化为这个问题？

Answer 1

我相信这是 NP-hard 因为如果你能解决你的问题，那么你就可以解决 minimum vertex cover .

证明草图

方法是定义一个矩阵，每个顶点有一列，每条边有一行。

在第 j 行中，对应于顶点 x 和 y 之间的一条边，将每个元素置为 0，除了在列 x 和 y 处放置一个 1。

如果我们可以选择 P 列使得行总和的最大值 <= 1，那么我们知道剩余的列对应于原始图的顶点覆盖。

(行总和 <= 1 意味着所选的 P 列最多只能包含 x 和 y 中的 1 个，因此我们的顶点覆盖中必须至少包含 x 和 y 中的 1 个。)

通过使用二分法，我们可以计算出满足此条件的最大 P，从而推断出最小顶点覆盖的大小。