# Return to Question

Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Post Undeleted by D.W.
Post Deleted by Brainpower2049
2 deleted 3 characters in body

Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.

Consider the Interval Scheduling problem. We have seen that the “earliest deadline-first” greedy algorithm finds an optimal set of jobs.

Consider now the “shortest-job-first” greedy algorithm, which initially sorts the jobs by increasing duration — i.e., so that f(1)−s(1) ≤ f(2)−s(2) ≤ 1 . . . ≤ f(n)−s(n). It then considers the jobs in this order; each job considered is added to a set A (initially empty) if it does not conflict with any job currently in A. Thus, at the end, the algorithm has produced a set of non-conflicting jobs A. (In contrast, the “earliest-finish-time-first” algorithm initially sorts the jobs by increasing finish time — i.e., so that f(1) ≤ f(2) ≤ . . . ≤ f(n). Other than the initial sorting of jobs, the two algorithms are the same.) We have seen that the “shortest-job-first” greedy algorithm does not necessarily produce an optimal set of jobs.

In this problem you must prove that it produces a set of feasible jobs whose size is at least half the size of an optimal set. Thus, in some sense, the set of jobs produced by this algorithm is not too bad compared to the optimum. (Contrast this to the “earliest-start-time-first” algorithm, which produces a set of jobs whose size can be an arbitrarily small fraction of the optimal.) More precisely, let m be the size of an optimal set of jobs, and let A be the set of jobs computed by the shortest-job first greedy algorithm. Prove that |A| ≥ m/2.

Hint. Let B be any optimal set of jobs and j be any job in A. What is the maximum number jobs in B with which j conflicts?

Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.

Consider the Interval Scheduling problem. We have seen that the “earliest deadline-first” greedy algorithm finds an optimal set of jobs.

Consider now the “shortest-job-first” greedy algorithm, which initially sorts the jobs by increasing duration — i.e., so that f(1)−s(1) ≤ f(2)−s(2) ≤ 1 . . . ≤ f(n)−s(n). It then considers the jobs in this order; each job considered is added to a set A (initially empty) if it does not conflict with any job currently in A. Thus, at the end, the algorithm has produced a set of non-conflicting jobs A. (In contrast, the “earliest-finish-time-first” algorithm initially sorts the jobs by increasing finish time — i.e., so that f(1) ≤ f(2) ≤ . . . ≤ f(n). Other than the initial sorting of jobs, the two algorithms are the same.) We have seen that the “shortest-job-first” greedy algorithm does not necessarily produce an optimal set of jobs.

In this problem you must prove that it produces a set of feasible jobs whose size is at least half the size of an optimal set. Thus, in some sense, the set of jobs produced by this algorithm is not too bad compared to the optimum. (Contrast this to the “earliest-start-time-first” algorithm, which produces a set of jobs whose size can be an arbitrarily small fraction of the optimal.) More precisely, let m be the size of an optimal set of jobs, and let A be the set of jobs computed by the shortest-job first greedy algorithm. Prove that |A| ≥ m/2.

Hint. Let B be any optimal set of jobs and j be any job in A. What is the maximum number jobs in B with which j conflicts?

Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.

Consider the Interval Scheduling problem. We have seen that the “earliest deadline-first” greedy algorithm finds an optimal set of jobs.

Consider now the “shortest-job-first” greedy algorithm, which initially sorts the jobs by increasing duration — i.e., so that f(1)−s(1) ≤ f(2)−s(2) ≤ . . . ≤ f(n)−s(n). It then considers the jobs in this order; each job considered is added to a set A (initially empty) if it does not conflict with any job currently in A. Thus, at the end, the algorithm has produced a set of non-conflicting jobs A. (In contrast, the “earliest-finish-time-first” algorithm initially sorts the jobs by increasing finish time — i.e., so that f(1) ≤ f(2) ≤ . . . ≤ f(n). Other than the initial sorting of jobs, the two algorithms are the same.) We have seen that the “shortest-job-first” greedy algorithm does not necessarily produce an optimal set of jobs.

In this problem you must prove that it produces a set of feasible jobs whose size is at least half the size of an optimal set. Thus, in some sense, the set of jobs produced by this algorithm is not too bad compared to the optimum. (Contrast this to the “earliest-start-time-first” algorithm, which produces a set of jobs whose size can be an arbitrarily small fraction of the optimal.) More precisely, let m be the size of an optimal set of jobs, and let A be the set of jobs computed by the shortest-job first greedy algorithm. Prove that |A| ≥ m/2.

Hint. Let B be any optimal set of jobs and j be any job in A. What is the maximum number jobs in B with which j conflicts?

1

# Troubles understanding this Interval Scheduling question

Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question.

Consider the Interval Scheduling problem. We have seen that the “earliest deadline-first” greedy algorithm finds an optimal set of jobs.

Consider now the “shortest-job-first” greedy algorithm, which initially sorts the jobs by increasing duration — i.e., so that f(1)−s(1) ≤ f(2)−s(2) ≤ 1 . . . ≤ f(n)−s(n). It then considers the jobs in this order; each job considered is added to a set A (initially empty) if it does not conflict with any job currently in A. Thus, at the end, the algorithm has produced a set of non-conflicting jobs A. (In contrast, the “earliest-finish-time-first” algorithm initially sorts the jobs by increasing finish time — i.e., so that f(1) ≤ f(2) ≤ . . . ≤ f(n). Other than the initial sorting of jobs, the two algorithms are the same.) We have seen that the “shortest-job-first” greedy algorithm does not necessarily produce an optimal set of jobs.

In this problem you must prove that it produces a set of feasible jobs whose size is at least half the size of an optimal set. Thus, in some sense, the set of jobs produced by this algorithm is not too bad compared to the optimum. (Contrast this to the “earliest-start-time-first” algorithm, which produces a set of jobs whose size can be an arbitrarily small fraction of the optimal.) More precisely, let m be the size of an optimal set of jobs, and let A be the set of jobs computed by the shortest-job first greedy algorithm. Prove that |A| ≥ m/2.

Hint. Let B be any optimal set of jobs and j be any job in A. What is the maximum number jobs in B with which j conflicts?