(Algorithms) Show that the underlying structure of the unit-task scheduling prob
ID: 3775069 • Letter: #
Question
(Algorithms) Show that the underlying structure of the unit-task scheduling problem is a matroid.
In addition, explain the time complexity of a greedy algorithm that solves this problem.
- you can refer to section 16.5(textbook 'Introduction to algorithms)' to answer this question.
16.5 A task-scheduling problem An interesting problem that can be solved using matroids is the problem of optimally scheduling unit-time tasks on a single processor, where each task has a deadline along with a penalty that must be paid if the deadline is missed. The problem looks complicated, but it can be solved in a surprisingly Simple manner using a greedy algorithm A unit-time task is a job, such as a program to be run on a computer, that requires exactly one unit of time to complete. Given a finite set S of unit-time tasks, a schedule for S is a permutation of S specifying the order in Which these tasks are to be performed. The first task in the schedule begins at time 0 and finishes at time 1, the second task begins at time 1 and finishes at time 2, and so on The problem of scheduling unit time tasks with deadlines and penalties for a single processor has the following inputs a set S ta1, a2, an of n unit-time tasks a set of n integer deadlines di, d2, dn such that each di satisfies 1 di n and task ai is supposed to finish by time d, and a set of n nonnegative weights or penalties wl, we, Wn, such that we incur a penalty of Wi it task ai is not finished by time di and We incur no penalty if a task finishes by its deadline We are asked to find a schedule for S that minimizes the total penalty incurred for missed deadlines Consider a given schedule. We say that a task is late in this schedule if it finishes after its deadline. Otherwise, the task is early in the schedule. An arbitrary schedule can always be put into early-first form, in which the early tasks precede the late tasks. To see this, note that if some early task ai follows some late task aj, then we can switch the positions of ai and ai, and ai will still be early and ai will still be late We similarly claim that an arbitrary schedule can always be put into canonical form, in which the early tasks precede the late tasks and the early tasks are scheduled in orderExplanation / Answer
Matroid
(if and only if)
As we know, the system is matroid <=> for any cost function , the greedy algo MAX gives a maximum solution.
Coming to unit-task scheduling problem, Let S be the set of unit time task with deadline and C be the set of all indepedent subset of S. Then (S,C) is matroid.
=> Trivial according to the definition i.e If B belongs to C and A is a subset of B, then A belongs to C.
<= Consider two independent sets A and B with number of elements in B is greater i.e |A| < | B | . Let k be the largest t such that Nt(A) >= Nt(B): where Nt(A): number of tasks in A with deadlines t or earlier.
Then k<n and Nt(A) < Nt(B) for k+1 <= t < n . Then choose x such that Nt(A U {x}) = Nt(A) <=t where 1<=t < k
and Nt(A U {x}) = Nt(A) + 1 <= Nt(B) <=t for k+1 <=t <=n
which means If A,B belongs to C and |A|<|B|, then there exists x in BA such that A U {x} in C .
Hence (S,C) is a matroid therefor Unit task scheduling is a Matroid.
Greedy Algorithm takes O(n^2) time
1. Sort penalties in non-increasing order.
2. Find tasks of independent sets: If there exists a schedule for each task and no late task in the sets
3. Schedule tasks in a maximum independent set in order of nondecreasing deadlines.
4. Schedule other tasks (missing deadlines) at the end arbitrarily.
Since there are n task and each of the Independence check made by the Algorithm taskes O(n ) (Step 2) time, so Overall time complecity is O(n^2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.