Purdue University Graduate School
Browse

Online Covering: Efficient and Learning-Augmented Algorithms

Download (1.09 MB)
thesis
posted on 2022-08-30, 15:48 authored by Young-san LinYoung-san Lin

We start by slightly modifying the generic framework for solving online covering and packing linear programs (LP) proposed in the seminal work of Buchbinder and Naor (Mathematics of Operations Research, 34, 2009) to obtain efficient implementations in settings in which one has access to a separation oracle.


We then apply the generic framework to several online network connectivity problems with LP formulations, namely pairwise spanners and directed Steiner forests. Our results are comparable to the previous state-of-the-art results for these problems in the offline setting.


Further, we extend the generic frameworks to online optimization problems enhanced with machine-learning predictions. In particular, we present learning-augmented algorithms for online covering LPs and semidefinite programs (SDP), which outperform any optimal online algorithms when the prediction is accurate while maintaining reasonable guarantees when the prediction is misleading. Specifically, we obtain general online learning-augmented algorithms for covering LPs with fractional advice and general constraints and initiate the study of learning-augmented algorithms for covering SDPs.

Funding

NSF CCF-1910659

NSF CCF-1910411

History

Degree Type

  • Doctor of Philosophy

Department

  • Computer Science

Campus location

  • West Lafayette

Advisor/Supervisor/Committee Chair

Elena Grigorescu

Advisor/Supervisor/Committee co-chair

Thanh Nguyen

Additional Committee Member 2

Greg Frederickson

Additional Committee Member 3

Simina Branzei

Usage metrics

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC