We\'ve seen the Interval Scheduling Problem in chapter on Greedy algorithms. Her

Question

We've seen the Interval Scheduling Problem in chapter on Greedy algorithms. Here we consider a computationally much harder version of it that we'll call Multiple Interval Scheduling. As before, you have a processor that is available to run jobs over some period of time (e.g., 9am to 5pm). People submit jobs to run on the processor; the processor can only work on one job at any single point in time. Jobs in this model, however, are more complicated than we've seen in the past: each job requires a set of intervals of time during which it needs to use the processor. Thus, for example, a single job could require the processor from 10am to 11am, and again from 2pm to 3pm. If you accept this job, it ties up your processor during those two hours, but you could still accept jobs that need and other time periods (including the hours from 11am to 2pm). Now you are give a set of n jobs, each specified by a set of time intervals, and you want to answer the following question: For a given number k, is it possible to accept at least k of the jobs so that no two of the accepted jobs have any overlap in time? Show that Multiple Interval Scheduling is NP-complete.

Explanation / Answer

Given a graph G = (V; E) and k >=0, divide the interval 10 AM to 5 PM into m disjoint intervals, one corresponding to each edge in E. Now create n jobs one corresponding to each vertex in V . The intervals for the job corresponding to v in V are those corresponding to the edges incident on v in G. It is easy to see that two jobs conflict if they correspond to vertices that are adjacent in G. Thus a set of jobs can be scheduled exactly if the corresponding vertices form an independent set in G. Thus there is a set of at least k jobs that can be scheduled i there is an independent set of size at lest k in G.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.