Scheduling question

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
wrongrook
Posts: 254
Joined: Sat Oct 17, 2009 9:39 pm

Scheduling question

Post by wrongrook » Wed Aug 17, 2011 5:27 pm

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?

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Scheduling question

Post by thundre » Thu Aug 18, 2011 8:10 pm

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.
Image

wrongrook
Posts: 254
Joined: Sat Oct 17, 2009 9:39 pm

Re: Scheduling question

Post by wrongrook » Thu Aug 18, 2011 8:44 pm

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.

Post Reply