# Bipartite allocation with minimum cost

Given two vertex sets $$V_1$$ and $$V_2$$. The vertices in $$V_2$$ have a limitation on the maximum degree of each vertex being $$K$$. I need to find an allocation algorithm such that every pair of vertices in $$V_1$$ is interconnected via a vertex in $$V_2$$ i.e $$X \leftrightarrow Y \leftrightarrow Z$$ , where $$X,Z \in V_1$$ and $$Y \in V_2$$.

The goal is to find an allocation that minimizes the distances between all such pairs in $$V_1$$. The distance is measured as : $$\; dist(X, Y) + dist(Y, Z)\;$$. The distances are provided beforehand. I kind of came up with an algorithm, but it doesn't guarantee optimality. Any help will be appreciated.

• Say exactly what you want to minimize. The largest distance? The average distance? – Brendan McKay Mar 15 at 7:29
• The total of all shortest distances between all pairs of vertices from set V1 – Aizen Mar 15 at 14:12
• This problem isn't clearly written out OP. It is very hard to follow your question. – Mike Mar 19 at 15:43
• @Mike can you point out which part was unclear. I added an image, but for some reason it's not there in the question anymore. – Aizen Mar 20 at 17:32
• @Mike here is the link math.stackexchange.com/questions/3145081/… – Aizen Mar 20 at 17:33