finding the maximum sum in Matrix

0
votes

Input: A 2-dimensional NxN -symmetric Matrix - with NxN positive elements.

Output: A 2-dimensional matrix of NxN size with N selected elements such that its summation is the maximum among all possible selection. Other elements that are not selected are zero. In other words, we should select N elements from matrix to return maximum sum.

Requirement: If the dimension of matrix is 4*4, we should select 4 integer. Every row and column in matrix should not be used more than 2 times. For example if we have 4*4 matrix, the following element could be selected:

(1,2)
(2,3)
(3,4)
(4,1)

but if we select (1,2)and (4,1), we cannot select (1,3), because we used 1 two times.

IS there an efficient algorithm for this problem?

1
algorithmmatrixsummaxdynamic-programming
Is there an efficient algorithm to get someone else to do my homework? – Marcus Müller
It is not homework, it is just part of my project. I just need the name of algorithm. – Arezu Tehrani
Can we select 12, 23, 34, 14? – David Eisenstat
yes we can select them. – Arezu Tehrani

1 Answers

0
votes

This problem is in that weird place where it's not obvious that there's a solution polytope with integral vertices and yet its similarity to general matching discourages me from looking for an NP-hardness reduction. Algorithms for general matching are complicated enough that modifying one would be a daunting prospect even if there were a way to do it, so my advice would be to use an integer program solver. There's a formulation like

maximize sum_{ij} w_{ij} x_{ij}
subject to
sum_{ij} x_{ij} = n
forall k, sum_i x_{ik} + sum_j x_{kj} ≤ 2
forall ij, x_{ij} in {0, 1},

where w_{ij} is the ijth element of the weight matrix.