Fewest number of classes for everyone to attend: polynomial-time solution?

Admin 1
Viewed 66

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?

np mathematical-optimization complexity-theory algorithm
2 Answers

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.

user_11393930

I have implemented the enumeration I suggested in my comment to the post by Peter de Rivaz. For speed, I use a bitset representation of the combinations. Each bit represents a day, and a 1-bit means the teacher lectures that day. I use an algorithm called Gosper's hack.

Again, the advantage of this enumeration strategy is that the combinations appear in increasing order of the number of days. It means the enumeration may stop at the first feasible combination because it represents the minimal number of days the teacher must lecture.

For a teaching period of 4 four days, my test program outputs:

All 1-subsets of a 4-set
0001
0010
0100
1000
All 2-subsets of a 4-set
0011
0101
0110
1001
1010
1100
All 3-subsets of a 4-set
0111
1011
1101
1110
All 4-subsets of a 4-set
1111
---

The test program is in the C++ language. The bitset representation is an unsigned integer. It has 32 bits, but the algorithm needs an extra bit. So the maximum number of days is 31, which fits the bill this time. On my computer, the 31-day case takes 16 seconds (with no bitset printing).

#include <iostream>
#include <string>
#include <algorithm> 
#include <cmath>

template<typename T>
T gosper_start(int k) noexcept {    // first k-subset
    return (T{1} << k) - T{1};
}

template<typename T>
T gosper_next(T x) noexcept {   // next k-subset
    const T s = x & (T{0} - x); // avoids x & -x (because the unary minus may issue a compiler warning)
    const T r = s + x;
    return r | (((x^r) >> 2) / s);
}

template<typename T>
T gosper_stop(int n) noexcept { // the n-set limit
    return T{1} << n;
}

template<typename T> 
std::string bitset_to_string(T x, int n) { // string representation of bitset
    std::string s{};
    while (n-- > 0) {
        s += (x & 1) ? "1" : "0";
        x >>= 1;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

void test() {
    using T = unsigned int; // the bit-set type
    const int N = 4;        // the n-set is a 4-set
    const T L = gosper_stop<T>(N); // the n-set limit
    
    for (int k=1; k<=N; ++k) { // all k from 1 to N
        std::cout << "All " << k << "-subsets " << "of a " << N << "-set" << std::endl;
        for (T s = gosper_start<T>(k); s < L; s = gosper_next<T>(s)) { // all k-subsets
            std::cout << bitset_to_string(s,N) << std::endl;
        }
    }
    std::cout << "---" << std::endl;
}
Admin1
Related