Maximize pairings subject to distance constraint

Question

I have a list of people's locations on a world map and want to pair nearby people up such that the number of pairs is maximized.

For example, subject to the constraint that paired people are within d=10 miles of each other, I might find 742 pairs from a list of n=3000 people's locations.

Possible considerations:

• alright to assume the world is a 2D Euclidean plane

• alright to assume n < 100000

• the distance constraint can be relaxed, for example to a cost function with a high value after 10

• as in real life, people cluster in cities, so there might be many people "0 miles apart" in New York City while people in Wyoming are few and far apart.

• any leads on the same problem above but for triplets would be great. That is, the same problem, but instead of two you take three people and group them together, preferably with the constraint still being that the three are contained in a d-diameter disc, though other similar constraints are fine.

A simple approach

• calculate all-pairs distances.

  • in the process create an array of pairs sorted from closest to farthest

  • in the process, for each person, store a list of people within d miles

• greedily pair together the closest unpaired people

• repeat the following until no progress has been made for a certain number of loops

  • find an unpaired person p_1 with closest person p_2 <= d miles of them. person p_2 is currently paired to person p_3.

  • unpair p_2 and p_3 and pair p_1 and p_2. If any exist, pair p_3 to a closest person p_4 that is unpaired and within d miles.

I'm sure there are many interesting approaches to this problem, and would any love input on what research/search terms I could look into to learn more about it, any ideas for algorithms to solve this, and possibly bounds on how well the above algorithm would work on the problem.

Thank you

Answer 1

You can formulate this as a maximum matching problem in an undirected graph, and then apply standard algorithms for this problem, such as Edmonds' algorithm. These algorithms are reasonably efficient and should be fast for your parameters, and they are guaranteed to find the optimal collection of pairings.

In particular, the graph is as follows. You have a vertex for each person. Draw an edge between two people if they are within 10 miles of each other. Now, you want a maximum matching in this undirected graph: i.e., a collection of edges (pairs of people) such that no two edges have a vertex in common (each person is paired up with at most one other person), and that is as large as possible.

There's lots written on the maximum matching problem; a search should turn up plenty of additional information.