Return to search

Online Covering: Efficient and Learning-Augmented Algorithms

<p>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.</p>
<p><br></p>
<p>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.</p>
<p><br></p>
<p>Further, we extend the generic frameworks to online optimization problems enhanced with <strong>machine-learning predictions</strong>. In particular, we present <strong>learning-augmented</strong> 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.</p>

  1. 10.25394/pgs.20063561.v1
Identiferoai:union.ndltd.org:purdue.edu/oai:figshare.com:article/20063561
Date14 June 2022
CreatorsYoung-san Lin (12868319)
Source SetsPurdue University
Detected LanguageEnglish
TypeText, Thesis
RightsCC BY 4.0
Relationhttps://figshare.com/articles/thesis/Online_Covering_Efficient_and_Learning-Augmented_Algorithms/20063561

Page generated in 0.0017 seconds