嗨,我正在处理以下问题.
给出一个大小为M x N且具有正系数的矩阵.目标是选择P列,使得得到的M×P矩阵的每一行中的所有元素的最大和最小化.例如,如果M = 3,N = 5,P = 2并且矩阵由下式给出
一个11一12一13一14一15
一21一22一23一24一25
一31一32一33 `一个34一35
最佳解决方案是选择`第2列和第4列,得到的矩阵由下式给出
a 12 a 14
a 22 a 24
a 32 a 34
并且在所有P列选择中,值max {a 12 + a 14,a 22 + a 24,a 32 + a 34 }是最小的.
由于存在(N over P)解决方案,人们可以实现一个简单的指数算法来解决这个问题,但是有没有更快的多项式时间解决方案呢？
或者,如果没有,任何人都可以肯定地证明这是一个NP难题吗？你知道任何类似的NP难题可能会减少到这个吗？