Task-scheduling problem as a matroid

A task-scheduling problem as a matroid

An interesting problem that can be solved using matroid is the problem of optimally scheduling unit-time tasks on a single processor, where each task has a deadline, along with a penalty paid if the task misses its deadline.

            Given a finite set S of unit-time tasks, a schedule for S is a permutation of S specifying the order in which to perform these tasks.

            The problem of scheduling unit-time tasks with deadlines and penalties for a single processor has the following inputs:

·         a set S = {a₁, a₂, . . . ,a_n} of n unit-time tasks;

·         a set of n integer deadlines d₁, d₂, . . . ,d_n, such that each d_i satisfies 1 ≤ d_i ≤ n and task a_i is supposed to finish by time di; and

·         a set of n non negative weights or penalties w₁,w₂, . . . ,w_n, such that a penalty of w_i is incurred if task a_i is not finished by time d_i.

The problem is to find a schedule for S that minimizes the total penalty incurred for missed deadlines.

A task is said to be late in this schedule if it finishes after its deadline. Otherwise, the task is early in the schedule.

The search for an optimal schedule is to finding a set A of tasks that are early in the optimal schedule. Having found set A, create the actual schedule by listing the elements of A in order of monotonically increasing deadlines, then listing the late tasks (i.e., S - A) in any order, producing a canonical ordering of the optimal schedule.

The set A of tasks is independent if there exists a schedule for these tasks such that no tasks are late. Clearly, the set of early tasks for a schedule forms an independent set of tasks because if the tasks in set A are scheduled in order of monotonically increasing deadlines then no task is late.

Theorem

Therefore, a greedy algorithm can be used to find a maximum-weight independent set of tasks A.

And according to theorem of correctness of greedy algorithm on matroids.

Example:

Matroids and greedy methods

 Matroids and greedy methods

Matroids were first described in 1935 by the mathematician Hassler Whitney as a combinatorial generalization of linear independence of vectors—‘matroid’ means ‘something sort of like a matrix’.

Many problems that can be correctly solved by greedy algorithms can be described in terms of an abstract combinatorial object called a matroid.

In terms of independence, a finite matroid ${\displaystyle M}$ has following properties:

1. The empty set is independent, i.e., ${\displaystyle \emptyset \in {\mathcal {I}}}$. Alternatively, at least one subset of ${\displaystyle E}$ is independent, i.e., ${\displaystyle {\mathcal {I}}\neq \emptyset }$.
2. Every subset of an independent set is independent, i.e., for each ${\displaystyle A'\subseteq A\subseteq E}$, if ${\displaystyle A\in {\mathcal {I}}}$ then ${\displaystyle A'\in {\mathcal {I}}}$. This is sometimes called the hereditary property.
3. If ${\displaystyle A}$ and ${\displaystyle B}$ are two independent sets (i.e., each set is independent) and ${\displaystyle A}$ has more elements than ${\displaystyle B}$, then there exists ${\displaystyle x\in A\backslash B}$ such that ${\displaystyle B\cup \{x\}}$ is in ${\displaystyle {\mathcal {I}}}$. This is sometimes called the augmentation property or the independent set exchange property.
4. 
   

5. If A is an independent subset in a matroid M, we say that A is maximal if it has no extensions. That is, A is maximal if it is not contained in any larger independent subset of M. The following property is often useful. All maximal independent subsets in a matroid have the same size.

Weighted matriod:

A matroid is weighted if it is associated with a weight function w that assigns a strictly positive weight w(x) to each element x Є S. The weight function w extends to subsets of S by summation:

 for any 

Greedy algorithms on a weighted matroid

Theorem: ( Correctness of the greedy algorithm on matroids)

Many problems for which a greedy approach provides optimal solutions can be formulated in terms of finding a maximum-weight independent subset in a weighted matroid.

Given a weighted matroid , and to find an independent set A such that w(A) is maximized can be done by following algorithm.

The algorithm takes as input a weighted matroid with an associated positive weight function w, and it returns an optimal subset A. The algorithm is greedy because it considers in turn each element x Є S, in order of monotonically decreasing weight, and immediately adds it to the set A being accumulated if  is independent. The entire algorithm runs in time O(n lg n + n f (n)).

Example: