The Power of Amortized Recourse for Online Graph Problems

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].