I’m going to devote a few posts to my thesis topic, the quadratic assignment problem. Quadratic assignment problems are a type of matching problem that are NP hard and have some interesting applications. I’ll start out by describing linear assignment problems, which are simpler but still fun.
As the name suggests, in a linear assignment problem objects in one set are to be assigned to an equal number of objects in a second set. The cost of assigning objects in the first set to objects in the second set are given, and the objective is to find the assignment that minimizes the total assignment cost. For example, the problem may be to assign workers to jobs so as to minimize the total amount of working time. A more formal description of the problem can be found on this page (and I recommend the book, BTW).
LAP can also be posed as the problem of finding the minimum cost matching on a bipartite graph. For this reason, in algorithms texts this problem is also sometimes referred to as “minimum cost weighted bipartite matching”. LAPs are linear programs and so they can be solved in polynomial time. As the wikipedia article on the problem states, there are algorithms that take advantage of the special structure of LAP to solve them more efficiently than general purpose LP solvers.
Next time I’ll go through one possible solution approach for LAP.