Department Seminar Series
The Power of Amortized Recourse for Online Graph Problems
23rd May 2023, 13:00
Ashton Lecture Theatre
Dr. Hsiang-Hsuan (Alison) Liu
Utrecht University
Abstract
In this work, we study online graph problems with monotone-sum objectives. We propose a general two-fold greedy algorithm that references yardstick algorithms to achieve t-competitiveness while incurring at most 1+O(1/t) amortized recourse. We further show that the general algorithm can be improved for three classical graph problems by carefully choosing the referenced algorithm and tuning its detailed behavior. For IndependentSet, we refine the analysis of our general algorithm and show that t-competitiveness can be achieved with 1+1/(t-1) amortized recourse. For MaximumCardinalityMatching, we limit our algorithm's greed to show that t-competitiveness can be achieved with even smaller amortized recourse. For VertexCover, 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 remark that this online result can be used as an offline approximation result (without violating the unique games conjecture to partially improve upon the constructive algorithm of Monien and Speckenmeyer).
Biography
Hsiang-Hsuan (Alison) Liu is a tenured Assistant Professor in the Department of Information and computing sciences at Utrecht University, associated with the Algorithms and Complexity Group. Before joining Utrecht University, she obtained her Dual PhD in Computer Science from the University of Liverpool (UK) and National Tsing Hua University (Taiwan) in 2017 under the supervision of Professor Prudence W.H. Wong and Professor Wing-Kai Hon. From 2017 to 2019, she was a postdoc of Dr Marcin Bienkowski at the University of Wroclaw (Poland).
Additional Materials
Maintained by Othon Michail