A teacher needs to give a mandatory class to every student in a class. The class must happen in a given month, say June, and everyone must attend this class exactly once.

Since students have various availability, not everybody is available everyday (the teacher is available every day). The teacher have everyone's availability for June, and wish to schedule as few classes as possible to cover everyone.

What is a good algorithm for this?

The one I can think of is to model this as a minimum set cover problem, where each set represents a particular day, and each node represents a student. A student is in a set if he is available on that day. The goal would be to select minimum number of sets so that every node is covered.

Since minimum set cover does not have a polynomial solution (other than an approximate one), is there a polynomial solution to this problem?

CodePudding user response：

If this is a real problem, then because there are at most 31 days in a month, it is feasible to do a brute force enumeration of all possible days to have classes and check for each if all students are covered and which has the smallest number of classes.

This is technically a polynomial solution as it depends linearly on the number of students. (It depends exponentially on the number of days, but this is limited by 31 so can be treated as a large constant.)

If you also want it to be polynomial in the number of days, then this is equivalent to the (unresolved) P=NP question because your analogy with set cover works both ways. In other words, if you could solve this problem in polynomial time, then you could solve any set cover decision problem in polynomial time (with an appropriate choice of students and classes), and set cover is NP-complete, so you could solve any NP complete problem in polynomial time.