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.
Our work:
| 
top