Title: Coffman-Sethi conjecture in multiprocessor scheduling
| Speaker: | Levent Tuncel |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Ron
Graham's
work,
during
the
late
1960s,
on
proving
that
LPT
(Longest
Processing
Time)
list
scheduling
algorithm
has
the
worst-case
approximation
ratio
of
precisely
$4/3
-1/(3m)$
(where
$m$
is
the
number
of
machines)
has
been
inspirational
in
the
areas
of
approximation
algorithms
as
well
as
in
scheduling
theory.
Inspired
by
this
work,
Coffman
and
Sethi
proposed
an
extension
of
this
algorithm
for
a
refinement
of
the
underlying
problem
and
a
conjecture
on
its
worst-case
approximation
ratio:
$(5m-2)/(4m-1)$,
in
1976.
This
conjecture
stayed
open
for
39
years.
In
this
talk,
I
will
discuss
a
proof
of
this
conjecture.
Our
proof
of
the
conjecture
designs
and
uses
techniques
somewhat
analogous
to
those
used
in
(graph
minors
based)
structural
graph
theory.
This
talk
is
based
on
two
joint
papers:
one
with
M.
Huang
and
P.
Ravi
(2013)and
the
other
with
P.
Ravi
(2015).