2
$\begingroup$

I have a set of points (tiny triangles) $K=\{1,2,\ldots, k\}$ and a set points (tiny circles) $N=\{1,2,\ldots, n\}$ and a matrix of positive real values $\mathbf{D}=\left[d_{ij}\right]$ for all $i\in K$ and for all $j\in N$. The entry of the matrix $d_{ij}$ can be viewed as the Euclidean distance between triangle $i$ and circle $j$.

I would like to assign the triangles to the circles with the constraint that each assigned point is assigned to its closest neighbor. Also, the assignment must be one-to-one. For example, let

$$ \mathbf{D}=\begin{pmatrix} 1 & 1 & 5\\ 2 & 3 & 1\\ 5 & 8 & 6 \end{pmatrix}. $$ Now:

  • triangle 1 would like to be assigned to circle 1 or 2 and then 3 (we have a tie);
  • triangle 2 would like to be assigned to circle 3 then 1 and then 2;
  • triangle 3 would like to be assigned to circle 1 then 3 and then 2;

How can I solve this problem?

I thought of creating a list of preferences based on $\mathbf{D}$ like in the example:

  • List of preference for triangle 1: 1, 2, 3
  • List of preference for triangle 2: 3, 1, 2
  • List of preference for triangle 3: 1, 3, 2

But how can I continue on solving this?

$\endgroup$
  • $\begingroup$ Do you really need this lists or do you the peferfect compromise (i.e. the best possible assignment of triangles to circles)? If it is the latter you might want to read about Bipartite Matching: en.wikipedia.org/wiki/Bipartite_graph#Matching $\endgroup$ – Martin Glauer Jun 16 '16 at 19:27
3
$\begingroup$

You have an instance of a bipartite matching problem. There are some variations on the problem. I think you're looking for a minimum cost bipartite matching, but maybe you're looking for a stable matching.

$\endgroup$
3
$\begingroup$

Your problem statement is not very clear about whether the constraints are hard or soft.

Hard constraints

Suppose the constraints are hard: each triangle must be assigned to one of the closest circles (there might be multiple possibilities, in case of a tie), and vice versa. For example triangle 1 can only be matched to circle 1 or 2; triangle 2 can only be matched to circle 3; triangle 3 can only be matched to circle 1. Then this problem can be solved in polynomial time.

Build a bipartite edge with one vertex for each triangle and one vertex for each circle. Draw an edge $(u,v)$ between triangle $u$ and circle $v$ if $u$ is one of the closest neighbors to $v$, and $v$ is one of the closest neighbors to $u$.

Then, you are looking for a perfect matching in this bipartite graph. There are efficient algorithms for this problem.

Soft constraints

Your first step will be to more precisely specify the desired solution. You list multiple goals, but some of these might be contradictory or in tension, and you'll need to decide how to trade off between them.

One way to do this is to specify a single objective function. An objective function takes a candidate solution as input and assigns a "value" (a real number) to it. Then, the optimization problem is to find the solution that maximizes the objective function.

With that approach, the way to solve this will depend on the specific objective function you have in mind. You should first develop a specific objective function. Then, take a look at weighted bipartite matching, the assignment problem, and stable matching, to see if any of those meet your needs. If you've chosen an objective function that none of those techniques are able to maximize, ask a new question and specify the precise objective function you are trying to maximize.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.