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.
For the specific application of traffic signal control, we simulate our simple K2,2 algorithm on a traffic network with Poisson arrivals at the edges of the network and Robertson's platoon dispersion model within the network. In some cases, our simple algorithm achieves significant improvements over actuated control.
(Practice job interview talk.)