Is it possible to keep the best of both worlds of the k-mean and k-medoid methods?

I need to form teams (clusters) of individuals in such a way as to minimize the distance between the locations of the individuals on the same team. I could therefore use the k-mean method.

Where it gets complicated is that the teams are made up of two kinds of individuals: team leaders and employees, with one team leader per team, no more and no less.

The k-mean method doesn't seem to me to be suited to the problem at hand, since it doesn't allow us to ensure that there is 1 team leader per team.

I thought we could use the k-medoids method, with each team leader being a medoid. There would then be one team leader per team. The problem is that, a priori, this method minimizes the distance between the team leader and his employees, but not the distance between all the members of the same team, as is the case with the k-mean method.

I tried to use the k-mean method, but it didn't allow me to have one team leader per team. With the k-medoid method, there is one team leader per team, but I'm not sure that the solution is optimal in the sense that the intra-group distance (team leader and employees combined) is minimised.

Hence my questions :

• Are my intuitions correct?
• If so, is it possible to have the "best of both worlds" of the k-mean and k-medoid methods with a method that both minimizes intra-team distance and ensures that there is one team leader per team?
• If it exists, what is the name of this algorithm?

Thanks for your help.

Using k-medoids seems appropriate in this use case. Selecting the team leaders as the initial medoids is correct. Iterating through the algorithm allows those initial medoids to move around to find the optimum distance between all team members.

There could be a case where the optimum solution would move a medoid so much that a group would no longer have a team member in it. You'd have to modify the algorithm to check for that condition possibly and prevent it.