Optimal pairing of bike with person - seeking proof of algorithm

0
votes

So this is an algorithm question. The problem statement is the following: given two lists of coordinates (or length n each) of bikes and people on a 2D grid (or a 2D grid that show the positions of each bike and person), calculate the optimal pairing of the bikes and people so that the total Manhattan distance of all the pairs are minimized. It is guaranteed that for each person, the distance to all bikes won't be the same and same applies for each bikes.

There is a solution in this question, which states that we can sort all the distances from low to high and pair the bike to the person if they are both unpaired. The complexity is obviously O(n^2 logn) time and O(n^2) space.

So my questions are

  1. Is this the optimal way and why? Can someone prove its optimality? If it's not optimal, what would be the optimal algorithm in minimizing the total distance?
  2. How is it related to the stable marriage problem?

Update:

The question linked is using a different criteria of priority. So what would be the algorithm that calculates the optimal pairing if the criteria is minimizing total Manhattan distance (except for the brute force DFS algorithm that is exponential in complexity)?

Update 2:

If the criteria is that no pair would prefer each other than their current partner, then it's a stable marriage problem. If the criteria is the total sum of distances, Hungarian algorithm should be used.

1
algorithmsortingproof
The question you've linked is using different bike assignment criteria; solutions to that problem do not necessarily solve your problem. – user2357112 supports Monica
(It's not entirely clear what the assignment criteria for that question are supposed to be, since "Closest person to the bike, get the bike at the first priority." is nowhere near as completely specified as that questioner seems to think, but it seems to be a local optimality condition, not the global condition you've given.) – user2357112 supports Monica
I see my mistake - posted an update in the question – Kevin He

1 Answers

3
votes

The sorting algorithm computes a stable marriage, because whenever a pair is formed, every neighbor is either available or in a pairing of no lesser desirability.

Stable marriage is not optimal. The bike and person at distance 2 would rather be with each other, which forces the pairing of the bike and the person at distance 9. The total cost is 11, which is worse than 3 + 4 = 7.

    B
  2 |3
B---P
|4
P

An optimal algorithm is to compute pairwise distances and run the Hungarian algorithm to compute a minimum-cost perfect matching.