Geodesic
Ronald Graham: laying the foundations of online optimization
Documenta mathematica, Optimization Stories (2012), pp. 239-245.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

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.
Classification : 68M20, 68Q25, 68R99, 90B35
Keywords: scheduling, makespan minimization, algorithm, competitive analysis 
@article{DOCMA_2012__S3__a18,
     author = {Albers, Susanne},
     title = {Ronald {Graham:} laying the foundations of online optimization},
     journal = {Documenta mathematica},
     pages = {239--245},
     publisher = {mathdoc},
     volume = {Optimization Stories},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a18/}
}
TY  - JOUR
AU  - Albers, Susanne
TI  - Ronald Graham: laying the foundations of online optimization
JO  - Documenta mathematica
PY  - 2012
SP  - 239
EP  - 245
VL  - Optimization Stories
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a18/
LA  - en
ID  - DOCMA_2012__S3__a18
ER  - 
%0 Journal Article
%A Albers, Susanne
%T Ronald Graham: laying the foundations of online optimization
%J Documenta mathematica
%D 2012
%P 239-245
%V Optimization Stories
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a18/
%G en
%F DOCMA_2012__S3__a18
Albers, Susanne. Ronald Graham: laying the foundations of online optimization. Documenta mathematica, Optimization Stories (2012), pp. 239-245. http://geodesic.mathdoc.fr/item/DOCMA_2012__S3__a18/