Online algorithms in resource management and constraint satisfaction

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2012-11-30
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2012
Major/Subject
Mcode
Degree programme
Language
en
Pages
130
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 133/2012
Abstract
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.

Toisin kuin klassisissa optimointimalleissa, käytännön optimointiasetelmissa on usein merkittäviä ajasta riippuvia epävarmuustekijöitä. Tähän puutteeseen voidaan vastata online-optimoinnin mallilla. Online-optimointitehtävissä ongelman syöte tulee tunnetuksi vaiheittain ajan myötä, mutta tämän epävarmuuden mallintamiseen ei käytetä todennäköisyysjakaumia. Tulevaisuuden informaation puutteen vuoksi hyvissäkin ratkaisuissa on väistämättä jälkikäteen tunnistettavia epäoptimaalisuuksia. Online-algoritmien suorituskykyä mitataan kilpailusuhteella, joka on pahimpaan mahdolliseen tapaukseen perustuva mittari. Tässä väitöskirjassa ja sen osajulkaisuissa esitetään ja analysoidaan uusia algoritmeja viidelle online-optimointitehtävätyypille. Esitetyillä algoritmeilla on parhaat tunnetut kilpailusuhteet kussakin ongelmassa. Eräkoon määritys- ja tallennuspaikkamalleissa todistetaan, että parhailla mahdollisilla algoritmeilla on olennaisesti sama kilpailusuhde kuin esitetyillä algoritmeilla.
Description
Supervising professor
Orponen, Pekka, Prof.
Thesis advisor
Orponen, Pekka, Prof.
Keywords
online algorithm, approximation algorithm, competitive analysis, combinatorial optimization, online-algoritmi, approksimointialgoritmi, kilpailullinen analyysi
Other note
Parts
  • [Publication 1]: Lauri Ahlroth, André Schumacher, Harri Haanpää. On the power of lookahead in online lot-sizing. Operations Research Letters, 38(6):522-526, November 2010.
  • [Publication 2]: Lauri Ahlroth, Pekka Orponen, André Schumacher. Approximate Data Aggregation and Prize-Collecting Steiner Trees. Submitted to Theoretical Computer Science, 28 pages, under review, March 2012.
  • [Publication 3]: Lauri Ahlroth, André Schumacher, Pekka Orponen. Online Bin Packing with Delay and Holding Costs. Accepted for publication in Operations Research Letters, 6 pages, October 2012.
  • [Publication 4]: Lauri Ahlroth, Olli Pottonen, André Schumacher. Approximately uniform online checkpointing with bounded memory. Invited to Algorithmica special issues of 17th Annual International Computing and Combinatorics Conference, 13 pages, under review, December 2011.
  • [Publication 5]: Lauri Ahlroth, Pekka Orponen. Unordered Constraint Satisfaction Games. In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, LNCS Volume 7464, pages 64-75, August 2012.
Citation