Page 1 of 1

Scheduling question

Posted: Wed Aug 17, 2011 5:27 pm
by wrongrook
Suppose I have 100 vectors, each vector V(i) containing a few integers V(i)=[v(i,0),v(i,1),v(i,2),...].
Given a value for N, is there an efficient algorithm for computing an offset x(i) for each vector such that all the integers v(i,j)+x(i) %N are unique?
(Or telling if the problem is impossible!)

For example,
V(0)=[0,1,2]
V(1)=[0,1]
has a solution x(0)=0, x(1)=3 for N=5, but is impossible for N=4.

It feels like I should be able to find a nice n^3 network flow algorithm or prove it is NP complete, but I can't decide which...

Any ideas?

Re: Scheduling question

Posted: Thu Aug 18, 2011 8:10 pm
by thundre
I think you can make some modifications to simplify:
  • Order within a given "vector" does not matter, so consider each V(i) a "set" of integers.
  • Only the value mod N of each integer matters, so 0 <= V(i,j) < N and 0 <= x(i) < N.
  • If [x0,x1] is a solution, so is [x0+1, x1+1]. So you can assume x0=0 and quickly calculate other solutions at the end, rather than searching for them.
If (sum of the sizes of all sets) > N, as it is with your N=4 example, a solution is impossible (based on the pigeon-hole principle). This can be quickly checked.

The brute-force algorithm would be something like O(100^N), but pruning might make it viable.

You could represent sets as bit-masks and use bit-rotation operations to calculate compatibility if N matches a supported word size on your processor.

Re: Scheduling question

Posted: Thu Aug 18, 2011 8:44 pm
by wrongrook
Thanks Thundre, everything you suggest sounds very sensible.

I've also been wondering about modelling it as a graph where there is a cluster of 100 fully connected vertices for each vector (each vertex represents a different offset for the vector). I would then add links between vertices in different clusters if the vectors are incompatible with those offsets.

I would then search for the maximum independent set for this graph http://en.wikipedia.org/wiki/Independent_set_problem as I think each independent set represents a solution to the problem with a certain number of vectors, so if I can find a set with one vertex from each cluster I have a solution to the problem.

Unfortunately, this problem is known to be NP-hard for a general graph...

What I don't know is whether my problem has enough extra structure for there to be a polynomial algorithm.