August 23, 2024 03:25

I've looked up about Munkres in the past and from what I've read, the two things he is known for his books, especially topology, and for some an algorithm I didn't bother to look up at the time.

Now that the uni semester is finally over, I tried tackling some of my small programming projects, and I found myself needing to solve an interesting problem. For a given $m \times n$ matrix, I need to extract a subset of its entries, such that every row and column has at most one chosen entry (and containing as many rows/columns as possible, which means we're choosing $k$ elements, where $k$ is the minimum between $m$ and $n$), while minimizing their total sum.

Turns out the so-called Munkres assignment algorithm does exactly what this problem describes. Like, it has nothing to do with topology, it's pretty much a very crazy coincidence. I don't know how it works though, I just imported a library for now.