1
$\begingroup$

I'm trying to find an efficient algorithm for the following problem:

Given two different sets, both of size $N$. Each element in the two sets has coordinates $(x,y)$. The task is to optimize the pairings between these two sets such that the maximum distance between the paired elements given a pairing, is minimized. I have only found algorithms that deal with the squared sum of all distances between paired elements or the smallest distance between any two points from the two different sets.

For example: Given a list of $N$ pair of points that are associated with locations $(x_0,y_0), (x_1,y_1), (x_2,y_2),\dotsc,( x_{n-1},y_{n-1})$, name them $a_0,a_1,a_2,\dotsc,a_{N-1}$ accordingly.

And another list of $N$ pairs of different points (locations) $(x_0,y_0), (x_1,y_1), (x_2,y_2),\dotsc,( x_{n-1},y_{n-1})$, name them $b_0,b_1,b_2,\dotsc,b_{N-1}$ accordingly.

How can I pair all elements (each element is a pair of points) from list 1 $(a_0,a_1,a_2\dotsc,a_{N-1})$ to the other elements in list 2 $(b_0,b_1,b_2,\dotsc,b_{N-1})$ so that we chose the shortest distances? eventually, I'd need to print the maximum distance among all minimum distances (that we have found for each of the elements).

Any idea how can this be achieved in reasonable run time? or name an algorithm that might help here.

$\endgroup$

1 Answer 1

3
$\begingroup$

You can solve this bottleneck assignment problem via integer linear programming as follows. Let $d_{i,j}$ be the distance between $a_i$ and $b_j$. Let binary decision variable $z_{i,j}$ indicate whether $a_i$ is paired with $b_j$. Let $m$ represent the maximum distance between paired elements. The problem is to minimize $m$ subject to linear constraints: \begin{align} \sum_j z_{i,j} &= 1 &&\text{for all $i$} \tag1 \\ \sum_i z_{i,j} &= 1 &&\text{for all $j$} \tag2 \\ m &\ge d_{i,j} z_{i,j} &&\text{for all $i$ and $j$} \tag3 \\ \end{align} Constraint $(1)$ matches $a_i$ to exactly one $b_j$. Constraint $(2)$ matches $b_j$ to exactly one $a_i$. Constraint $(3)$ enforces $z_{i,j}=1 \implies m \ge d_{i,j}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .