Does anyone know if this is polynomially solvable?

Question

Hi, I'm dealing with the following problem.

You are given a matrix of size M x N with positive coefficients. The goal is to choose P columns such that maximal sum of all elements in each row of the resulting M x P matrix is minimized. For example, if M = 3, N = 5, P = 2 and matrix is given by

a₁₁ a₁₂ a₁₃ a₁₄ a₁₅
a₂₁ a₂₂ a₂₃ a₂₄ a₂₅
a₃₁ a₃₂ a₃₃`a₃₄ a₃₅

and the optimal solution is to choose `columns 2 and 4, the resulting matrix is given by

a₁₂ a₁₄
a₂₂ a₂₄
a₃₂ a₃₄

and the value max{a₁₂ + a₁₄, a₂₂ + a₂₄, a₃₂ + a₃₄} is minimal among all choices of P columns.

Since there are (N over P) solutions, one can implement an easy exponential algorithm to solve this problem, but is there any faster, polynomial-time solution to this?

Or, if there is not, can anyone surely prove this is an NP-hard problem? Do you know any similar NP-hard problem that might be reduced to this one?

Answer 1

I believe this is NP-hard because if you could solve your problem, then you could solve minimum vertex cover.

Sketch of proof

The approach would be to define a matrix with a column for each vertex and a row for each edge.

In row j, corresponding to an edge between vertices x and y, put every element to 0, except at columns x and y place a 1.

If we can choose P columns such that the max of the row sums are <= 1, then we know that the remaining columns correspond to a vertex cover of the original graph.

(The rows sum being <= 1 means that the P columns selected can only contain at most 1 of x and y, and so at least 1 of x and y must be included in our vertex cover.)

By using bisection we could work out the largest P for which this is true, and hence deduce the size of the minimum vertex cover.