Online algorithms in resource management and constraint satisfaction

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Orponen, Pekka, Prof.
dc.contributor.author Ahlroth, Lauri
dc.date.accessioned 2013-07-12T09:00:07Z
dc.date.available 2013-07-12T09:00:07Z
dc.date.issued 2012
dc.identifier.isbn 978-952-60-4825-3 (electronic)
dc.identifier.isbn 978-952-60-4852-9 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/10460
dc.description.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. en
dc.description.abstract 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. fi
dc.format.extent 130
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 133/2012
dc.relation.haspart [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.
dc.relation.haspart [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.
dc.relation.haspart [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.
dc.relation.haspart [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.
dc.relation.haspart [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.
dc.subject.other Computer science en
dc.title Online algorithms in resource management and constraint satisfaction en
dc.title Online-algoritmeja resurssienhallintaan ja rajoiteongelmille fi
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.school School of Science en
dc.contributor.department Tietojenkäsittelytieteen laitos fi
dc.contributor.department Department of Information and Computer Science en
dc.subject.keyword online algorithm en
dc.subject.keyword approximation algorithm en
dc.subject.keyword competitive analysis en
dc.subject.keyword combinatorial optimization en
dc.subject.keyword online-algoritmi fi
dc.subject.keyword approksimointialgoritmi fi
dc.subject.keyword kilpailullinen analyysi fi
dc.identifier.urn URN:ISBN:978-952-60-4825-3
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.contributor.supervisor Orponen, Pekka, Prof.
dc.opn Woeginger, Gerhard J., Prof., Eindhoven University of Technology, The Netherlands
dc.rev Koivisto, Mikko, Dr., University of Helsinki, Finland
dc.rev Villanger, Yngve, Dr., University of Bergen, Norway
dc.date.defence 2012-11-30


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse