CODEWITHSUNDEEP
algorithmcombinatorics
Almacomet
Almacomet

Reputation: 211

Maximizing sum subject to different indicies

Suppose I have a matrix, A, of size n x p with n > p, each element of 0 <= A <= 1. I would like to find p elements in A, one in each column, such that the overall sum is maximized and each element is in a different row. Thus, there are n permute p different combinations to consider. Is there a name for this problem? I found ones such as the knapsack problem, but the setup is different. Additionally, are they are any efficient algorithms to compute this for say n=300, p=10? There are a few special cases to check, such as if the max in each column so happens to be on a different row. Otherwise, am I left to dynamic programming? Thanks!

Upvotes: 1

Views: 59

Answers (1)

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

This is maximum matching in a weighted bipartite graph, also known as the assignment problem. Columns and rows are graph parts (resp. agents and tasks) and cells are edges (resp. task assignments).

This is effectively solved by the Hungarian algorithm which is polynomial.

Upvotes: 1

Related Questions