# Maximize pairings subject to distance constraint

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

• Generally speaking, if you want to group $k$ people together you want to find the largest (edge-wise) subgraph $G'$ so that $\Delta(G') < k$. As you described, finding a solution for $k = 2$ (pairs of people) is equivalent to finding a maximum matching since it is the largest subgraph of maximum degree $1$. How would you proceed for different values of $k$? – Roukah Jun 7 '17 at 8:26
• @Roukah, I don't know. We could call it the disjoint $k$-cliques problem, I suppose. I don't know if it has been studied in general graphs, or in this particular kind of graph. Sounds worth asking separately as a new question! – D.W. Jun 7 '17 at 14:33