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

Question

嗨,我正在处理以下问题.

给出一个大小为M x N且具有正系数的矩阵.目标是选择P列,使得得到的M×P矩阵的每一行中的所有元素的最大和最小化.例如,如果M = 3,N = 5,P = 2并且矩阵由下式给出

一个₁₁一₁₂一₁₃一₁₄一₁₅
一₂₁一₂₂一₂₃一₂₄一₂₅
一₃₁一₃₂一₃₃ `一个₃₄一₃₅

最佳解决方案是选择`第2列和第4列,得到的矩阵由下式给出

a ₁₂ a ₁₄
a ₂₂ a ₂₄
a ₃₂ a ₃₄

并且在所有P列选择中,值max {a ₁₂ + a ₁₄,a ₂₂ + a ₂₄,a ₃₂ + a ₃₄ }是最小的.

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

或者,如果没有,任何人都可以肯定地证明这是一个NP难题吗？你知道任何类似的NP难题可能会减少到这个吗？

Answer 1

我相信这是NP难的,因为如果你可以解决你的问题,那么你可以解决最小顶点覆盖.

证明草图

方法是定义一个矩阵,每个顶点有一列,每个边有一行.

在行j中,对应于顶点x和y之间的边缘,将每个元素设置为0,除了列x和y放置1.

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

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

通过使用二分法,我们可以得出最大的P,这是真的,因此推导出最小顶点覆盖的大小.