ICS 269, Winter 1997: Theory Seminar
3 Jan 1997:
Probabilistic Analysis of Scheduling with Conflicts
Vitus J. Leung, ICS,
UC Irvine
We consider the scheduling of jobs that may be competing for
mutually exclusive resources. We model the conflicts between jobs
with a "conflict graph", so that all concurrently running jobs must
form an independent set in the graph. This model is natural and
general enough to have applications in a variety of settings;
however, we are motivated by the following two specific
applications: traffic intersection control and session scheduling
in high speed local area networks with spatial reuse. Our goal is
to bound the maximum completion time of any job in the system. It
has been previously shown that the best competitive ratio
achievable by any online algorithm for the maximum completion time
on interval or bipartite graphs is Omega(n), where n
is the number of nodes in the conflict graph. As a result, we study
scheduling with conflicts under probabilistic assumptions about the
input. Each node i has a value pi such
that a job arrives at node i in any given time unit with
probability pi. Arrivals at different nodes and
during different time periods are independent. We focus on
distributions where the expected time to complete the jobs that
arrive in a single time unit is less than 1. Under these
assumptions, we are able to obtain a bounded competitive ratio for
an arbitrary conflict graph. In addition, if the conflict graph is
a perfect graph, we give an algorithm whose competitive ratio
converges to 1.
(Practice talk for a SODA '97 paper
with Sandy Irani.
Conference proceedings version
available from Vitus' website.)