4

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.

  • 2
    So the players don't get to rest between gigs. Ask an union representative. – Tulains Córdova Jul 2 '14 at 20:51
  • @user61852 - except for the cowbell player, who probably doesn't get to play – Dan Pichelman Jul 2 '14 at 21:07
  • 2
    @DanPichelman unless the bands Needs More Cowbell™. – s.m Jul 2 '14 at 21:14
  • 1
    @user61852: the context is that of a music workshop in which, each evening, students who have known each other for 10+ years and meet once a year, get to play a couple of tunes together. So resting is not a concern. Also, said musicians will be up till 4 in the morning jamming anyway ;) – s.m Jul 2 '14 at 21:18
  • I will ask for a few clarifications before I look more into this problem. At start and end, how do you calculate cost. The way I see it is to have each band represented by a binary string 010001 with length the same as the number of players. So is there a cost of 2 at the beginning with my 010001 example? Also if 01000 is the last one is there a cost of 1 when moving them off the stage?. In general, in a switch of 01010 and 10101, what is your cost definition is it 5 (as the distance between those 2 strings) is it 2 (the number of 1 bits turning to zero?)? – InformedA Jul 4 '14 at 4:19
2

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.

| improve this answer | |
  • Ah, but you've just shown it's reducible to TSP. But this graph is fairly special - every node is connected to every other node and the triangle rule applies (cost of switching a A to C as AC is at most AB + BC). Question is - does this make it simpler? Now if you could provide a reduction of general TSP to this, that would be awesome – Ordous Jul 3 '14 at 11:07
  • @Ordous: yes, you are right, my answer is just a hint how the problem could be attacked, there might be a better approach. If you know one, feel free to post an answer. – Doc Brown Jul 3 '14 at 11:23
  • @Doc Brown It's not even obvious that this is an isomorphism of TSP though. The way I see it is that this can be very well be a poly one until one can prove a reduction. I am thinking in that direction (poly time) since there is a range cap of the cost (number of players * number of bands). This cap range has poly relationship with this input. Even that this is not easy at all. – InformedA Jul 3 '14 at 13:25
  • 1
    You can reduce from Hamiltonian Path, by having a band for each vertex and putting for each edge a musician in the two bands of its endpoints. So the problem is NP-hard. – Falk Hüffner Jul 14 '14 at 13:57
0

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.
| improve this answer | |
  • It looks like the second part of the answer can be reduced to: "Make start and end the same vertex and find Hamiltonian Cycle(also NP-hard)". But I'm not following the first part. That seems to be answering the question of "Is there a lineup that allows one member change per band change?", and not the minimization. Also - what happens if a band has 2 unique people that don't play anywhere else? Or are you including non-existent bands? (In which case this solution becomes even more cryptic) – Ordous Aug 29 '14 at 10:26
  • @Ordous The first part is the problem for the decision version. In which you ask is there an ordering of bands to have a certain on-stage staying value. It is not an optimization problem, so there is no minimization involve. For your second question, that is not a concern you should have because the poly-reduction direction is not in that way. – InformedA Aug 29 '14 at 10:33
  • To clarify: You are showing here that Hamiltonian is reducible to the decision problem, hence, since the optimization problem is at least as hard as the decision problem and is reducible to NP-hard TSP, then the original optimization problem is SNP? – Ordous Aug 29 '14 at 10:43
  • Yes to your first question, they are all NP-complete all reducible to each other. I am not certain of how you define SNP. But you can solve the optimization using the decision problem's solution. – InformedA Aug 29 '14 at 10:59

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.