# ICS 269, Spring 1997: Theory Seminar

## 23 May 1997:

Final Public Oral Dissertation Defense

Vitus Leung, ICS, UC Irvine

In this dissertation, we develop a model for scheduling jobs
that may be competing for mutually exclusive resources. The
conflicts between jobs are modeled by a *conflict graph*, so
that the set of 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. For all the graphs we address, we
focus on the problem of minimizing the maximum response time of any
job that enters the system. For the specific graph which arises in
the traffic intersection control problem, we show a simple
algorithm which achieves the optimal competitive ratio. Motivated
by the second application, we also give an algorithm for interval
graphs.

Since I have already presented some of the details in the upper
bounds, I will be presenting some of the details in the lower
bounds. The best competitive ratio achievable by any online
algorithm even on a path of *n* nodes is Omega(*n*). As a
result, we turn to scheduling with conflicts under probabilistic
assumptions about the input. Each node *i* has a value *
p*_{i} such that a job arrives at node *i* in any
given time unit with probability *p*_{i}. Arrivals at
different nodes and during different time periods are independent.
Under reasonable assumptions on the input sequence, 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.

Finally, we discuss simulation results for the traffic signal
control problem. Using the methodology of Recker, Ramanathan, Yu,
and McNally and a modification of their software, we show that some
of our algorithms achieve significant improvements over
full-actuated control, the most advanced traffic signal control
method in the public domain.