Найти множество столбцов, максимизирующих минимум суммы в каждой строке

Question

Учитывая матрицу A, я ищу набор p столбцов, который максимизирует минимум на сумму совпадающих ячеек в каждой строке.

Например: если р = 2 и А =

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-решатель для простой формулировки целочисленной программы, где c(j) равно 1, если взят j-й столбец, и 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