I am asking for help for the following problem.
- N items. Each Item has to be put into exactly one bin.
- C constraints. Each constraints is a pair of items, meaning item x und item y are not allowed in the same bin.
- There is no limit the the capacity of the bins.
- Goal: Minimum number of bins.
Background
The items are exams. And there are students. The exams of one student may not be on the same day (= bin), these are the constraints. Each student has approx. 3-10 exams. Goal: Minimum number of exam-days.
What I did
If you randomly limit each exam to 2 bins, then this problem can be coded as 2-SAT and be solved in polynomial time.
Question
Is there a polynomial time algorithm for this variation of bin packing? May with dynamic programming, because each student has at most 10 exams?
Edit 1
While thinking about it, it may be converted to a maximum bipartite matching problem.
Left Nodes: The Exams E1, E2, E3, ....
Right Nodes: The "Exams times bins". E1B1, E1B2, E1B3, .... E2B1, E2B2, ...
Each Exam (e.g. E1) is only connected to its own bins (E1B1, E1B2, ...). This is just a thought. Now we have the problem that the following assigment E1-E1B2 and E2-E2B2 may be forbidden, if E1 and E2 may not be in the same bin (B2).
One could add (left) dummy-nodes connecting exactly two of the right nodes. DummyA to E1B1 and E2B1, DummyB to E1B2 and E2B2, ... . This looked good first, but I think its not working, because the dummy-nodes are to many. They need to have higher priority than the "E to EB" edges, and will "destroy" valid solutions.
Thank you for your help Benjamin
This is precisely the question of finding the chromatic number of the graph whose vertex set is N and whose edge set is C.
https://en.wikipedia.org/wiki/Graph_coloring
It is NP-complete to determine whether 3 bins suffice.