Which algorithms do I need to look into?

Question

First things first: I need to apologize in advance about the bad choice of title for this question, but I really couldn't come up with something meaningful. I'm actually looking for suggestions as to what this kind of problem in called, so that I can do some research on my own. I will gladly change the title once the suggestions will start to come in.

It's not even a real problem, it's just an exercise I made up in order to explore algorithms I have never had the chance to deal with.

Let's say we want to write a program that will help us to optimize the logistics of an arbitrary number of music bands that have to perform one after the other on the same stage during the same night.

Here's the problem: the bands share players, meaning that any given player can play in more than one band. Were the bands all made of different players, we wouldn't need a program at all, but since all the musicians know each other, they will form many bands with different combinations of them.

What we want to do is to arrange all the bands in such a way that groups that share the greatest number of members will "cluster" together and play one after the other, so that we can minimize the number of musicians involved with each change of band. In other words, the largest number possible of musicians should be already on stage each time a band finishes its set and the next one comes on stage.

Is this just another form of the famous staff rostering / scheduling problem?

Or is it simpler?

I admittedly haven't yet though hard about how one might solve it, it's just a problem that I thought of today.

If I had to take a stab at it, it looks like the problem boils down to figuring out which bands have the most members in common, and sort them accordingly.

But how is this called in CS parlance?

And, is that all there is to it?

Arranging bands by the number of musicians is the only requirement we have. I sense that, if we had to take into account other kinds of constraints like, say, one particular band would really prefer playing at the beginning and another right in the middle, this might turn into a full-fledged scheduling problem.

In its simplest form, though, this appears to be a simple problem but, like I said, I don't know the name of the family of algorithms that would enable me determine which bands have the most musicians in common.

Answer 1

This problem can be interpreted as a variant of the travelling salesman problem, as @randomA has noted in a comment. The bands form the nodes of a graph to be visited, the "distance" between two bands is the number of musicians they don't have in common (the number of musicians which has to change for a band change). The goal is to minimize the total cost of a tour through this graph.

Finding the number of uncommon members is easy: find the number of common members by using standard set intersection (see here) and substract the number 2 times from the sum of the number of members of the 2 bands.

To the question for the class of algorithms: TSP has been attacked by several dozen kinds of algorithms, see the Wikipedia article for some pointers. Some of them deliver an exact solution (but since the general problem is NP-hard, there are no "efficient" algorithms known working for all cases). Others deliver a "good" solution, which is not necessarily the optimium; such heuristics can be much faster.

Answer 2

This just comes to my mind as I was working with a different problem. When I came back I realized that Falk Huffner has already mentioned the tip.

Anyway, no more fingering, one can show the reduction as follows to the decision version of the problem (whether there is an ordering of bands so that you have a value x)

• First use a modified version of Hamiltonian path, in which you are given a start and end vertices.

Make each vertex a band and each edge a person. If there is a modified Hamiltonian path then obviously, there is an ordering that gives you value that is the number of bands - 1. The proof for the inverse is also not hard to see.

• The second part is about proving reduction between the modified Hamiltonian and the regular one. The idea is that one simply uses a vertex as starting candidate. Split this vertex into 2 vertices called start and end. For the start and end vertices, split again into outter nodes and inner nodes. The outer node will connect with all other nodes as in the original graph, the inner node connects only with the corresponding outer nodes. This ensures that once a path enters the start or end node the candidate node in the original graph is visited only once. Thus you have a Hamiltonian path iff there is a modified Hamiltonian path.