CODEWITHSUNDEEP
algorithmoptimizationheuristics
zouba
zouba

Reputation: 21

Find the set of columns maximizing the minimum of the sum in each row

Given a matrix A, i’m looking for the set of p columns that maximizes the minimum on the sum of the matched cells in each row.

For example: if p=2 and A=

1 2 4

3 0 3

5 6 2

Choosing C1 and C2 would give f=min(r1,r2,r3)=min(1+2; 3+0; 5+6)=3

While choosing C1 and C3 would give f=min(1+4; 3+3; 5+2)=5 which is the best choice.

Is there any algorithm or heuristic doing so..

Thanks

Upvotes: 2

Views: 502

Answers (1)

grar
grar

Reputation: 151

This problem is NP-hard via a trivial reduction from set cover (let A be the 0-1 matrix representing the element-set containment relation). I would try a MIP solver on the straightforward integer-program formulation, where c(j) is 1 if the jth column is taken and 0 otherwise.

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

Upvotes: 4

Related Questions