Here's an interesting problem. I would like to call this the family reunion problem. As far as I know, this problem hasn't been stated or generalized anywhere else. But maybe it has?

Suppose a set of people live in different cities and wish to have a reunion. They're fairly far apart such that they'll be flying, cost is an issue. Everyone is indifferent as to the city, but they wish to minimize the total travel cost of the trip.

The family consists of the following people:

  • Alice living in Boston
  • Bobby living in Miami
  • Cindy living in Los Angeles
  • David living in Seattle
  • Euclid living in San Francisco

Costs to fly between each city are given in this matrix:

BOS MIA LAX SEA
SFO 218 233 98 98
SEA 218 238 138
LAX 218 283
MIA 168

Which member of the family should host the reunion?

Of course this is easy with just 4 people, but family reunions usually have many times this. And family reunions don't necessarily have to be held in a home city; it could be an entirely new venue.

My intuition tells me this is NP-Complete, but it has been a while.