0
$\begingroup$

Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework is due tomorrow and I don't have this done yet and I'm freaking out!

This is the question:

Show that a greedy algorithm that schedules talks in a lecture hall, as described in Example 7, by selecting at each step the talk that overlaps the fewest other talks, does not always produce an optimal schedule.

Example 7: Suppose we have a group of proposed talks with preset start and end times. Devise a greedy algorithm to schedule as many of these talks as possible in a lecture hall, under the assumptions that once a talk starts, it continues until it ends, no two talks can proceed at the same time, and a talk can begin at the same time another one ends. Assume that talk j begins at time s_j (where s stands for start) and ends at time e_j (where e stands for end)

$\endgroup$
2
  • $\begingroup$ I think I might have solved it myself. If the algorithm is programmed to pick the fewest conflicts, it will do just that. It will pick the set of the fewest conflicts regardless of whether or not that set includes the most talks. I drew a stupid diagram. I think that answer is right. If it isn't let me know. $\endgroup$ Commented Sep 18, 2014 at 23:11
  • $\begingroup$ You omitted Example 7 $\endgroup$ Commented Sep 18, 2014 at 23:55

2 Answers 2

Reset to default
1
$\begingroup$

You need to show the whole problem-we don't have access to Example 7. What is the criterion for "optimum"? Is it the most talks scheduled without overlap, the highest utilization of the hall, or what? You are probably expected to show a list of talks, show what the greedy algorithm produces, and show a better solution (according to the criterion for optimum). Do the talks come with times they have to be given, or are you setting that. This can come from the order you consider the talks-you might scatter a few at various times of the day, preventing many others from being scheduled. If the talks cannot be moved in time, you might schedule a whole batch from the hour to hour plus 5 minutes (only 5 min long), while you have a bunch of hour talks that don't fit any more. If you had scheduled the hours first, you would use the hall all day.

$\endgroup$
1
  • $\begingroup$ Suppose we have a group of proposed talks with preset start and end times. Devise a greedy algorithm to schedule as many of these talks as possible in a lecture hall, under the assumptions that once a talk starts, it continues until it ends, no two talks can proceed at the same time, and a talk can begin at the same time another one ends. $\endgroup$ Commented Sep 18, 2014 at 23:00
1
$\begingroup$

Surprisingly the counter example of this algorithm is quite hard to find using pen. I spent many hours to study and cannot find a counter example. Here is a counter example I found from CS 473 notes online:

|----||----||----||----|
   |----||----||----|
   |----|      |----|
   |----|      |----|

Clearly the optimal solution is |----||----||----||----| which is 4 talks

But using the algorithm you will end up with |----| |----| |----| which is 3 only.

I think this algorithm can produce the optimal result when n <= 3 which I tried exhaustively. I tried some cases when n=4 and still cannot find a counter example.

I believe that this is the smallest N the counter example will appear, which is 11.

Reference: https://courses.grainger.illinois.edu/cs473/fa2010/Lectures/lecture11.pdf

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.