The Power of Amortized Recourse for Online Graph Problems

Alison Liu*, Jonathan Toole-Charignon

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

In this work, we study online graph problems with monotone-sum objectives, where the vertices or edges of the graph are revealed one by one and need to be assigned to a value such that certain properties of the solution hold. We propose a general two-fold greedy algorithm that augments its current solution greedily and references yardstick algorithms. The algorithm maintains competitiveness by strategically aligning to the yardstick solution and incurring recourse. We show that our general algorithm achieves t-competitiveness while incurring at most wmax⋅(t+1)t−1
amortized recourse for any monotone-sum problems with integral solution, where wmax
is the largest value that can be assigned to a vertex or an edge. For fractional monotone-sum problems where each of the assigned values is between [0, 1], our general algorithm incurs at most t+1wmin⋅(t−1)
amortized recourse, where wmin
is the smallest non-negative value that can be assigned. We further show that the general algorithm can be improved for three classical graph problems. For INDEPENDENT SET
, we refine the analysis of our general algorithm and show that t-competitiveness can be achieved with tt−1
amortized recourse. For MAXIMUM CARDINALITY MATCHING
, we limit our algorithm’s greed to show that t-competitiveness can be achieved with (2−t∗)(t∗−1)(3−t∗)+t∗−13−t∗
amortized recourse, where t∗
is the largest number such that t∗=1+1j≤t
for some integer j. For VERTEX COVER
, we show that our algorithm guarantees a competitive ratio strictly smaller than 2 for any finite instance in polynomial time while incurring at most 3.33 amortized recourse. We beat the almost unbreakable 2-approximation in polynomial time by using the optimal solution as the reference without computing it. We remark that this online result can be used as an offline approximation result (without violating the unique games conjecture [20]) to partially improve upon the constructive algorithm of Monien and Speckenmeyer [23].
Original languageEnglish
Title of host publicationApproximation and Online Algorithms
Subtitle of host publication20th International Workshop, WAOA 2022, Potsdam, Germany, September 8–9, 2022, Proceedings
EditorsParinya Chalermsook, Bundit Laekhanukit
Place of PublicationCham
PublisherSpringer
Pages134–153
Number of pages20
Edition1
ISBN (Electronic)978-3-031-18367-6
ISBN (Print)978-3-031-18366-9
DOIs
Publication statusPublished - 21 Oct 2022

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13538
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'The Power of Amortized Recourse for Online Graph Problems'. Together they form a unique fingerprint.

Cite this