algorithm - 找到使每行中总和的最小值最大化的列集

Question

给定一个矩阵 A，我正在寻找一组 p 列，它使每行中匹配单元格总和的最小值最大化。

例如:如果 p=2 且 A=

1 2 4

3 0 3

5 6 2

选择 C1 和 C2 将得到 f=min(r1,r2,r3)=min(1+2; 3+0; 5+6)=3

虽然选择 C1 和 C3 会给出 f=min(1+4; 3+3; 5+2)=5 这是最佳选择。

是否有任何算法或启发式这样做......

谢谢

Answer 1

这个问题是 NP 难的，通过从集合覆盖中进行简单的归约(让 A 是表示元素集包含关系的 0-1 矩阵)。我会在直接的整数规划公式上尝试 MIP 求解器，其中如果采用第 j 列，则 c(j) 为 1，否则为 0。

maximize lambda
subject to
lambda <= c(1) A(i,1) + ... + c(n) A(i,n)    for all i
c(1) + ... + c(n) = p
c(j) in {0, 1}                               for all j