Online optimization

Online optimization is the branch of optimization theory, studied in both computer science and operations research, that deals with problems where the decision maker does not have complete knowledge of future inputs at the time a decision must be made. This sets it apart from classical offline optimization, where the entire problem instance is known in advance. The field covers two broad situations: problems that call for a sequence of decisions as pieces of the input arrive one at a time, and problems that call for a single decision under uncertainty, such as the ski rental problem, where a person must decide whether to rent or buy equipment without knowing how many times they will use it. The standard way to judge an online algorithm's performance is competitive analysis, which compares its outcome against an optimal offline algorithm that is allowed to see the whole input in advance. Online optimization is usually distinguished from related frameworks such as robust optimization, stochastic optimization and Markov decision processes, and it includes well known formal problems such as the Canadian traveller problem, the k-server problem, job shop scheduling and the secretary problem, each with its own algorithmic solutions for coping with incomplete information.