Choosing office hours to maximise number of students who can attend at least one time slot

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
44
down vote

favorite
13












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):



$$beginarrayc
textName & 9 text am & 10 text am & 11 text am & 12 text pm \ hline
textAlice & 1 & 1 & 0 & 0 \
textBob & 1 & 1 & 0 & 1 \
textCharlotte & 1 & 1 & 0 & 1 \
textDaniel & 0 & 1 & 1 & 1 \
textEve & 0 & 0 & 1 & 1 \
textFrank & 0 & 0 & 1 & 0 \ hline
textTotal & 3 & 4 & 3 & 4
endarray$$



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?










share|cite|improve this question



















  • 9




    $binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
    – Misha Lavrov
    Sep 10 at 17:54






  • 6




    I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
    – lokodiz
    Sep 10 at 17:56






  • 3




    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)
    – smci
    Sep 10 at 23:00







  • 5




    Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
    – Eric Duminil
    Sep 11 at 6:39






  • 2




    @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).
    – Chieron
    Sep 11 at 15:03














up vote
44
down vote

favorite
13












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):



$$beginarrayc
textName & 9 text am & 10 text am & 11 text am & 12 text pm \ hline
textAlice & 1 & 1 & 0 & 0 \
textBob & 1 & 1 & 0 & 1 \
textCharlotte & 1 & 1 & 0 & 1 \
textDaniel & 0 & 1 & 1 & 1 \
textEve & 0 & 0 & 1 & 1 \
textFrank & 0 & 0 & 1 & 0 \ hline
textTotal & 3 & 4 & 3 & 4
endarray$$



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?










share|cite|improve this question



















  • 9




    $binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
    – Misha Lavrov
    Sep 10 at 17:54






  • 6




    I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
    – lokodiz
    Sep 10 at 17:56






  • 3




    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)
    – smci
    Sep 10 at 23:00







  • 5




    Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
    – Eric Duminil
    Sep 11 at 6:39






  • 2




    @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).
    – Chieron
    Sep 11 at 15:03












up vote
44
down vote

favorite
13









up vote
44
down vote

favorite
13






13





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):



$$beginarrayc
textName & 9 text am & 10 text am & 11 text am & 12 text pm \ hline
textAlice & 1 & 1 & 0 & 0 \
textBob & 1 & 1 & 0 & 1 \
textCharlotte & 1 & 1 & 0 & 1 \
textDaniel & 0 & 1 & 1 & 1 \
textEve & 0 & 0 & 1 & 1 \
textFrank & 0 & 0 & 1 & 0 \ hline
textTotal & 3 & 4 & 3 & 4
endarray$$



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?










share|cite|improve this question















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):



$$beginarrayc
textName & 9 text am & 10 text am & 11 text am & 12 text pm \ hline
textAlice & 1 & 1 & 0 & 0 \
textBob & 1 & 1 & 0 & 1 \
textCharlotte & 1 & 1 & 0 & 1 \
textDaniel & 0 & 1 & 1 & 1 \
textEve & 0 & 0 & 1 & 1 \
textFrank & 0 & 0 & 1 & 0 \ hline
textTotal & 3 & 4 & 3 & 4
endarray$$



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?







combinatorics optimization






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Sep 12 at 12:27

























asked Sep 10 at 17:51









lokodiz

1,4191719




1,4191719







  • 9




    $binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
    – Misha Lavrov
    Sep 10 at 17:54






  • 6




    I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
    – lokodiz
    Sep 10 at 17:56






  • 3




    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)
    – smci
    Sep 10 at 23:00







  • 5




    Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
    – Eric Duminil
    Sep 11 at 6:39






  • 2




    @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).
    – Chieron
    Sep 11 at 15:03












  • 9




    $binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
    – Misha Lavrov
    Sep 10 at 17:54






  • 6




    I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
    – lokodiz
    Sep 10 at 17:56






  • 3




    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)
    – smci
    Sep 10 at 23:00







  • 5




    Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
    – Eric Duminil
    Sep 11 at 6:39






  • 2




    @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).
    – Chieron
    Sep 11 at 15:03







9




9




$binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
– Misha Lavrov
Sep 10 at 17:54




$binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
– Misha Lavrov
Sep 10 at 17:54




6




6




I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
– lokodiz
Sep 10 at 17:56




I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
– lokodiz
Sep 10 at 17:56




3




3




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)
– smci
Sep 10 at 23:00





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)
– smci
Sep 10 at 23:00





5




5




Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
– Eric Duminil
Sep 11 at 6:39




Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
– Eric Duminil
Sep 11 at 6:39




2




2




@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).
– Chieron
Sep 11 at 15:03




@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).
– Chieron
Sep 11 at 15:03










3 Answers
3






active

oldest

votes

















up vote
58
down vote



accepted










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.






share|cite|improve this answer






















  • "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).
    – Martin Bonner
    Sep 11 at 11:41










  • @MartinBonner Good point. I have rephrased to make the statement more precise.
    – Misha Lavrov
    Sep 11 at 14:38










  • I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
    – qwr
    Sep 11 at 19:00










  • @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.
    – Misha Lavrov
    Sep 11 at 20:20


















up vote
8
down vote













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.






share|cite|improve this answer



























    up vote
    3
    down vote













    Practically speaking, simply vary the office hours each week.






    share|cite|improve this answer
















    • 2




      The risk here is low attendance because students end up confused about when your office hours are.
      – Misha Lavrov
      Sep 11 at 20:22










    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "69"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













     

    draft saved


    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2912164%2fchoosing-office-hours-to-maximise-number-of-students-who-can-attend-at-least-one%23new-answer', 'question_page');

    );

    Post as a guest






























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    58
    down vote



    accepted










    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.






    share|cite|improve this answer






















    • "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).
      – Martin Bonner
      Sep 11 at 11:41










    • @MartinBonner Good point. I have rephrased to make the statement more precise.
      – Misha Lavrov
      Sep 11 at 14:38










    • I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
      – qwr
      Sep 11 at 19:00










    • @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.
      – Misha Lavrov
      Sep 11 at 20:20















    up vote
    58
    down vote



    accepted










    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.






    share|cite|improve this answer






















    • "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).
      – Martin Bonner
      Sep 11 at 11:41










    • @MartinBonner Good point. I have rephrased to make the statement more precise.
      – Misha Lavrov
      Sep 11 at 14:38










    • I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
      – qwr
      Sep 11 at 19:00










    • @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.
      – Misha Lavrov
      Sep 11 at 20:20













    up vote
    58
    down vote



    accepted







    up vote
    58
    down vote



    accepted






    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.






    share|cite|improve this answer














    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.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Sep 11 at 14:37

























    answered Sep 10 at 18:26









    Misha Lavrov

    38.7k55195




    38.7k55195











    • "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).
      – Martin Bonner
      Sep 11 at 11:41










    • @MartinBonner Good point. I have rephrased to make the statement more precise.
      – Misha Lavrov
      Sep 11 at 14:38










    • I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
      – qwr
      Sep 11 at 19:00










    • @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.
      – Misha Lavrov
      Sep 11 at 20:20

















    • "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).
      – Martin Bonner
      Sep 11 at 11:41










    • @MartinBonner Good point. I have rephrased to make the statement more precise.
      – Misha Lavrov
      Sep 11 at 14:38










    • I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
      – qwr
      Sep 11 at 19:00










    • @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.
      – Misha Lavrov
      Sep 11 at 20:20
















    "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).
    – Martin Bonner
    Sep 11 at 11:41




    "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).
    – Martin Bonner
    Sep 11 at 11:41












    @MartinBonner Good point. I have rephrased to make the statement more precise.
    – Misha Lavrov
    Sep 11 at 14:38




    @MartinBonner Good point. I have rephrased to make the statement more precise.
    – Misha Lavrov
    Sep 11 at 14:38












    I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
    – qwr
    Sep 11 at 19:00




    I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
    – qwr
    Sep 11 at 19:00












    @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.
    – Misha Lavrov
    Sep 11 at 20:20





    @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.
    – Misha Lavrov
    Sep 11 at 20:20











    up vote
    8
    down vote













    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.






    share|cite|improve this answer
























      up vote
      8
      down vote













      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.






      share|cite|improve this answer






















        up vote
        8
        down vote










        up vote
        8
        down vote









        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.






        share|cite|improve this answer












        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.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Sep 10 at 18:14









        Acccumulation

        5,9362616




        5,9362616




















            up vote
            3
            down vote













            Practically speaking, simply vary the office hours each week.






            share|cite|improve this answer
















            • 2




              The risk here is low attendance because students end up confused about when your office hours are.
              – Misha Lavrov
              Sep 11 at 20:22














            up vote
            3
            down vote













            Practically speaking, simply vary the office hours each week.






            share|cite|improve this answer
















            • 2




              The risk here is low attendance because students end up confused about when your office hours are.
              – Misha Lavrov
              Sep 11 at 20:22












            up vote
            3
            down vote










            up vote
            3
            down vote









            Practically speaking, simply vary the office hours each week.






            share|cite|improve this answer












            Practically speaking, simply vary the office hours each week.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Sep 11 at 18:51









            user38230

            462




            462







            • 2




              The risk here is low attendance because students end up confused about when your office hours are.
              – Misha Lavrov
              Sep 11 at 20:22












            • 2




              The risk here is low attendance because students end up confused about when your office hours are.
              – Misha Lavrov
              Sep 11 at 20:22







            2




            2




            The risk here is low attendance because students end up confused about when your office hours are.
            – Misha Lavrov
            Sep 11 at 20:22




            The risk here is low attendance because students end up confused about when your office hours are.
            – Misha Lavrov
            Sep 11 at 20:22

















             

            draft saved


            draft discarded















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2912164%2fchoosing-office-hours-to-maximise-number-of-students-who-can-attend-at-least-one%23new-answer', 'question_page');

            );

            Post as a guest













































































            Popular posts from this blog

            How to check contact read email or not when send email to Individual?

            Displaying single band from multi-band raster using QGIS

            How many registers does an x86_64 CPU actually have?