I have a set $M$ of $n$ observations ${M_1, M_2,...M_n}$ and a set $C$ of $n$ existing "cases" ${C_1, C_2,...C_n}$.

There is a cost or distance metric for matching the observations to the cases, where each observation is matched to one and only one case. Generally, the cost is the sum of the costs associated with each edge connecting an observation and its corresponding case.

There are other cases I am interested in, where the number of observations is less than or greater than the number of cases. The objective is still to minimize the cost when completing the matching optimization.

I'm interested in the theory and the algorithms for minimizing the cost.In order to research this, I want to know what the correct terminology would be.


There are a few terminologies that you could go with here, but I would say that this is a minimum cost matching problem. In the case where the number of observations and cases are the same, this is an assignment problem. The Hungarian Algorithm is a well-known method of finding an optimal solution.

Given a graph $G=(V,E)$, a matching $A$ is a subset of edges such that no two edges in $A$ are incident to a common vertex. People are often interested in finding maximal and maximum matchings. $A$ is a perfect matching if every vertex $v \in V$ is incident to some edge $e \in A$. So some terminology you might be interested in is 'minimum cost matching'. For more information, take a look at the wikipedia page for matching.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.