49
$\begingroup$

I have the following (real world!) problem which is most easily described using an example.

I ask my six students when the best time to hold office hours would be. I give them four options, and say that I'll hold two hours in total. The poll's results are as follows (1 means yes, 0 means no):

$$\begin{array}{l|c|c|c|c} \text{Name} & 9 \text{ am} & 10 \text{ am} & 11 \text{ am} & 12 \text{ pm} \\ \hline \text{Alice} & 1 & 1 & 0 & 0 \\ \text{Bob} & 1 & 1 & 0 & 1 \\ \text{Charlotte} & 1 & 1 & 0 & 1 \\ \text{Daniel} & 0 & 1 & 1 & 1 \\ \text{Eve} & 0 & 0 & 1 & 1 \\ \text{Frank} & 0 & 0 & 1 & 0 \\ \hline \text{Total} & 3 & 4 & 3 & 4 \end{array}$$

Naively, one might pick columns 2 and 4, which have the greatest totals. However, the solution which allows the most distinct people to attend is to pick columns 2 and 3.

In practice, however, I have ~30 possible timeslots and over 100 students, and want to pick, say, five different timeslots for office hours. How do I pick the timeslots which maximise the number of distinct students who can attend?

$\endgroup$
12
  • 9
    $\begingroup$ $\binom{30}{5}$ is just $142506$, which is a small number for a computer. Why not use brute force? $\endgroup$
    – Misha Lavrov
    Sep 10, 2018 at 17:54
  • 7
    $\begingroup$ I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems $\endgroup$
    – lokodiz
    Sep 10, 2018 at 17:56
  • 3
    $\begingroup$ Re the formulation: Based on experience, it's much better instead of asking for a hard binary 1/0 is to have them soft-rank each timeslot from 0 (totally impossible, conflict) up to say 3 or 4 (ideal) $\endgroup$
    – smci
    Sep 10, 2018 at 23:00
  • 5
    $\begingroup$ Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software. $\endgroup$
    – Eric Duminil
    Sep 11, 2018 at 6:39
  • 2
    $\begingroup$ @smci : that solution might also solve a secondary problem: students who do not have that many choices overall might be more important to cover first in an algorithm like Misha's than those available all the time. compare Frank in the example above to Bob/Charlotte/Daniel (those 3 are irrelevant for the solution as they will always be covered when choosing 2 slots of 4). $\endgroup$
    – Chieron
    Sep 11, 2018 at 15:03

3 Answers 3

Reset to default
63
$\begingroup$

In general, this problem is the maximum coverage problem, which is NP-hard, so you're not going to be able to find the optimal solution by any method substantially faster than brute force. (As I mentioned, for a problem of your size, brute force is still feasible.)

However, a modification of your strategy (to choose the timeslots with the highest totals) performs reasonably well.

It doesn't actually make sense to choose all the timeslots with the highest totals immediately: if they all have the same students in them, then this isn't any better than just choosing one of the timeslots. Instead, we can:

  1. Choose one timeslot with the highest total number of students.
  2. Remove all students that can make it to that timeslot from consideration. Recalculate the totals for the remaining students.
  3. Repeat steps 1-2 until you have chosen $k=5$ timeslots.

According to the wikipedia article, this algorithm achieves an approximation ratio of $1 - \frac1e$; that is, if you can reach $N$ students with the optimal choice of timeslots, this algorithm will reach at least $(1 - \frac1e)N$ students.

There are other possible approximate solutions out there; for example, there is the big step heuristic, which considers all choices of $p$ timeslots in each step, as opposed to all individual timeslots. (When $p=1$, it is the algorithm above; when $p=k$, it is just brute force.) No fast algorithm has guaranteed performance better than $(1 - \frac1e)N$, but they may perform better in some cases.

$\endgroup$
4
  • $\begingroup$ "so you're not going to be able to do substantially better than brute force" That is very wrong. You can do much better than brute force (which will fail for large numbers) provided you don't need perfection (as you go on to show). $\endgroup$
    – Martin Bonner supports Monica
    Sep 11, 2018 at 11:41
  • $\begingroup$ @MartinBonner Good point. I have rephrased to make the statement more precise. $\endgroup$
    – Misha Lavrov
    Sep 11, 2018 at 14:38
  • $\begingroup$ I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples. $\endgroup$
    – qwr
    Sep 11, 2018 at 19:00
  • $\begingroup$ @qwr Different NP-hard problems have extremely different behavior when we try to approximate them, and extremely different average-case behavior (for instance, approximating the maximum independent set of a graph is hard in almost all cases). Not being an expert, I wouldn't want to say anything about this specific problem. The known hardness result here is that (assuming $P \ne NP$) no algorithm can guarantee a $(1 - \frac1e + \epsilon)$-factor approximation; this, of course, does not say anything about the average case. $\endgroup$
    – Misha Lavrov
    Sep 11, 2018 at 20:20
8
$\begingroup$

With those numbers, brute force is still feasible. You have 30 choose 5 = 142506 different combinations. I don't think there's any algorithm other than brute force that is guaranteed to get the best solution, but one heuristic would be to arrange the students in sets from least availability to most. Then rank time slots by how many of the least available students they match, then break ties by how many of second lest available, etc. Take the best time slot according to that criteria. Remove all students that can make that time slot, and apply the same algorithm to the remaining time slots and students, and continue until you've reached your maximum number of time slots. In your example, Frank is the least available student, so 11 am, as the only time slot he can make, is the first choice. This leaves Alice, Bob, and Charlotte without a time slot, and of them, Alice is the least available. 9 am and 10 am both accommodate Alice, so you can take either one (although if you take into account students that were removed in previous steps, then 10 am wins).

You can combine the two: use the heuristic until you get to small enough numbers that you're okay with using brute force.

Another heuristic is to look at clustering (is there one set of students that is mostly available in the morning, and another in the evening), and pick time slots in different clusters.

$\endgroup$
3
$\begingroup$

Practically speaking, simply vary the office hours each week.

$\endgroup$
1
  • 2
    $\begingroup$ The risk here is low attendance because students end up confused about when your office hours are. $\endgroup$
    – Misha Lavrov
    Sep 11, 2018 at 20:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .