Online Optimization

In classic optimization one assumes complete knowledge of all input data that define a problem instance. However, it is unlikely that in practice those information are available in advance. Decisions have to be made based on incomplete knowledge, instead. This dilemma/problem setting has motivated (among other directions) the research on online optimization.

In an online optimization problem the input is modelled as a (finite) sequence of requests which are supplied to the algorithm incrementally. Then, an online algorithm produces the output incrementally without knowing the complete input.

The quality of online algorithms is typically assessed by their worst-case performance, the so called competitive ratio. An algorithm for a minimization problem is c-competitive if its solution value does not exceed c times the optimal value for any instance.

This general idea of performance analysis in the online setting can be seen as a request-answer-game between the online algorithm and some adversary who generates the problem instance and serves it as an offline algorithm. The adversary tries to maximize its performance relative to the online player. This it is the debatable competition of an online algorithm with an all-knowing malicious adversary.