1
$\begingroup$

We are given coordinates of $n$ people and $m$ shops. We should find a matching such that each person is matched with exactly one shop, and one shop is matched with at most one person.The total cost of one matching is sum of all matchings, and for each matching its cost is calculated as Manhattan distance between those two points. It will always hold that $m > n$.

For me, this looks a lot like the bipartite matching problem, however I'm not sure what to do with the costs of the matchings. I started thinking about algorithms that starts with one trivial matching and update it if making some other matching decreases the cost. However, I'm not sure if this will work. What is the correct way to solve this problem. I don't have much experience with matching algorithms, so I'm not sure how to approach this problem.

$\endgroup$
3
$\begingroup$

Your problem is an instance of minimum bipartite perfect matching. This is known as the assignment problem, and there are known efficient algorithms.

As a first step, you should compute the weights of all edges, using the formula your are given (L1 distance between the point corresponding to the person and the point corresponding to the shop).

$\endgroup$
1
$\begingroup$

To convert your problem into minimum cost bipartite perfect matching, pad the smaller side with dummy vertices. Make your graph a complete bipartite graph where the cost of each edge is the Manhattan distance between the points, and all edges to the dummy vertices are large enough to essentially be infinity. Then you can use a standard assignment problem algorithm. The unmatched shops will be matched with the dummy vertices.

$\endgroup$

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.