Minimum cost to match $n$ people with $m$ shops 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 &gt; 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.
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).