Title: Coffman-Sethi conjecture in multiprocessor scheduling
| Speaker: | Levent Tuncel |
| Affiliation: | University of Waterl |
| Room | MC 6486 |
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,
Co
man
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).