Purdue University Graduate School
Online_Covering__Efficient_and_Learning_Augmented_Algorithms.pdf (1.09 MB)

Online Covering: Efficient and Learning-Augmented Algorithms

Download (1.09 MB)
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.


NSF CCF-1910659

NSF CCF-1910411


Degree Type

  • Doctor of Philosophy


  • 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