Online algorithms in resource management and constraint satisfaction

Lauri Ahlroth

    Research output: ThesisDoctoral ThesisCollection of Articles

    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.
    Translated title of the contributionOnline-algoritmeja resurssienhallintaan ja rajoiteongelmille
    Original languageEnglish
    QualificationDoctor's degree
    Awarding Institution
    • Aalto University
    Supervisors/Advisors
    • Orponen, Pekka, Supervising Professor
    • Orponen, Pekka, Thesis Advisor
    Publisher
    Print ISBNs978-952-60-4852-9
    Electronic ISBNs978-952-60-4825-3
    Publication statusPublished - 2012
    MoE publication typeG5 Doctoral dissertation (article)

    Keywords

    • online algorithm
    • approximation algorithm
    • competitive analysis
    • combinatorial optimization

    Fingerprint Dive into the research topics of 'Online algorithms in resource management and constraint satisfaction'. Together they form a unique fingerprint.

    Cite this