Stochastic Scheduling

Abstract:

The NP-completeness of a problem is defined with respect to the worst case analysis of the running time. The drawback of such an analysis is that few or even a single bad instance suffice to get bad bounds. Moreover, worst case examples often require quite intricate constructions and the performance of the given algorithm may be much better on 'typical' instances. Despite the wide acceptance of the worst case analysis there is hence a need for additional models which better capture such behavior. A natural approach is to consider the average case for certain distributions of the problem instances.

In the talk we show that the concept competitive ratio --- which is a typical worst case notion --- can be used also for an average case analysis. As a proof of concept we consider the problem of scheduling n jobs on m machines so that the sum of job completion times is minimized. Our analysis technique allows to also roughly estimate the probability distribution of the competitive ratio. Thus, our result bridges the gap between worst case complexity and average case complexity.