In contrast to classical optimization models, real-life optimization typically involves significant uncertainties over time. This gap is addressed by the framework of online optimization, where problem inputs are revealed only gradually over time but no probability distributions are assumed. Due to the initial lack of future information even good solutions inevitably have some inefficiencies that can be identified only in hindsight. The performance of online algorithms is typically measured by a worst-case measure: the competitive ratio. In this thesis and its publications we present and analyze several new algorithms for five types of online optimization problems: lot-sizing, data aggregation, checkpointing, bin packing with delay and holding costs, and games on Boolean formulas. The algorithms presented for the problems yield the currently best known competitive ratios. Essentially matching lower bounds for the best possible competitive ratios are proved in the lot-sizing and checkpointing models.
|Translated title of the contribution||Online-algoritmeja resurssienhallintaan ja rajoiteongelmille|
|Publication status||Published - 2012|
|MoE publication type||G5 Doctoral dissertation (article)|
- online algorithm
- approximation algorithm
- competitive analysis
- combinatorial optimization