An improved analysis of SRPT scheduling algorithm on the basis of functional optimization

The competitive performance of the SRPT scheduling algorithm has been open for a long time except for being 2-competitive, where the objective is to minimize the total completion time. Chung et al. proved that the SRPT algorithm is 1.857-competitive. In this paper we improve their analysis and show a 1.792-competitiveness. We clearly mention that our result is not the best so far, since Sitters recently proved the algorithm is 1.250-competitive. Nevertheless, it is still well worth reporting our analytical method; our analysis is based on the modern functional optimization, which can scarcely be found in the literature on the analysis of algorithms. Our aim is to illustrate the potentiality of functional optimization with a concrete application.

► We give an improved analysis of the SRPT algorithm though it is not the best so far.
► A linear program over an infinite-dimensional vector space is solved.
► We show the potentiality of functional optimization for the analysis of algorithms.