有人知道这个问题是否可以多项式时间内解决吗？

Question

3

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

给定一个大小为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₃₄

在所有选择P列的情况下，max{a₁₂ + a₁₄, a₂₂ + a₂₄, a₃₂ + a₃₄}的值最小。

虽然有(N over P)种解决方案，但可以实现一种简单的指数算法来解决这个问题，但是否有更快的多项式时间解决方案呢？

或者，如果没有，有人能够确定证明这是一个NP难问题吗？您是否知道任何类似的NP难问题可能会被归约到此问题？

- Angie CreepyCool

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

我认为这是NP难问题，因为如果您能解决您的问题，那么您就可以解决最小顶点覆盖。

证明概述

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

在第j行中，对应连接x和y的边，在除x和y处的每个元素都为0，而在x和y处放置1。

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

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

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