Ronald Graham: Laying the Foundations of Online Optimization

This chapter highlights fundamental contributions made by Ron Graham in the area of online optimization. In an online problem relevant input data is not completely known in advance but instead arrives incrementally over time. In two seminal papers on scheduling published in the 1960s, Ron Graham introduced the concept of \emph{worst-case approximation} that allows one to evaluate solutions computed online. The concept became especially popular when the term competitive analysis was coined about 20 years later. The framework of approximation guarantees and competitive performance has been used in thousands of research papers in order to analyze (online) optimization problems in numerous applications.

2010 Mathematics Subject Classification: 68M20, 68Q25, 68R99, 90B35

Keywords and Phrases: Scheduling, makespan minimization, algorithm, competitive analysis

Full text: dvi.gz 14 k, dvi 36 k, ps.gz 2916 k, pdf 248 k.

Home Page of DOCUMENTA MATHEMATICA