Introduction to Algorithms, Third Edition

release time
r
i
. Suppose also that we allow
preemption
, so
that a task can be suspended and restarted at a later time. For example, a task
a
i
with processing time
p
i
D
6
and release time
r
i
D
1
might start running at
time 1 and be preempted at time 4. It might then resume at time 10 but be
preempted at time 11, and it might finally resume at time 13 and complete at
time 15. Task
a
i
has run for a total of 6 time units, but its running time has been
divided into three pieces. In this scenario,
a
i
’s completion time is
15
. Give
an algorithm that schedules the tasks so as to minimize the average completion
time in this new scenario. Prove that your algorithm minimizes the average
completion time, and state the running time of your algorithm.

---

448
Chapter 16
Greedy Algorithms
16-3
Acyclic subgraphs
a.
The
incidence matrix
for an undirected graph
G
D
.V; E/
is a
j
V
j j
E
j
ma-
trix
M
such that
M
e
D
1
if edge
e
is incident on vertex
, and
M
e
D
0
other-
wise. Argue that a set of columns of
M
is linearly independent over the field
of integers modulo 2 if and only if the corresponding set of edges is acyclic.
Then, use the result of Exercise 16.4-2 to provide an alternate proof that
.E;
/
of part (a) is a matroid.
b.
Suppose that we associate a nonnegative weight
w.e/
with each edge in an
undirected graph
G
D
.V; E/
. Give an efficient algorithm to find an acyclic
subset of
E
of maximum total weight.
c.
Let
G.V; E/
be an arbitrary directed graph, and let
.E;
/
be defined so that
A
2
if and only if
A
does not contain any directed cycles. Give an example
of a directed graph
G
such that the associated system
.E;
/
is not a matroid.
Specify which defining condition for a matroid fails to hold.