BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T101632Z
UID:Seminar-dept-1050@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230523T130000
DTEND:20230523T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Hsiang-Hsuan (Alison) Liu: The Power of Amortized Recourse for Online Graph Problems\n\nIn 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).\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1050
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR