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 ソルバーを試してみます。ここで、 th 列が取得されc(j)た場合は 1、それ以外の場合は 0 です。j

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