Ronald Graham: laying the foundations of online optimization

Abstract

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 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.