BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Online TCP Acknowledgment under General Delays [Oberseminar Discre
 te Optimization]
DTSTART:20260817T161500Z
DTEND:20260817T171500Z
DTSTAMP:20260813T172700Z
UID:indico-event-1529@math-events.uni-bonn.de
DESCRIPTION:Speakers: William Umboh (University of Melbourne)\n\nWe revisi
 t the canonical online problem of TCP Acknowledgment (aka single-item lot 
 sizing): a sequence of n packets arrives over time\, and the objective is 
 to minimize both the number of acknowledgments sent and the total delay ex
 perienced by the packets. It is well-known that greedy\, which acknowledge
 s when the delay of pending packets equals the acknowledgment cost\, is 2
 ‑competitive.\nIn this work\, we consider more general delay cost models
  where the overall delay cost is not simply the sum of individual packet d
 elays. We show that for some natural delay cost models\, greedy is still 2
 -competitive. The most interesting setting is the batch-aware model where 
 the algorithm pays a delay cost per acknowledgment that depends on the pac
 ket delays of the acknowledged packets. We show that greedy has linear com
 petitive ratio\, and give a logarithmic competitive algorithm. Finally\, w
 e show that the latter is tight via a surprising connection to the Parking
  Permit problem. \nThis is joint work with Sujoy Bhore and Michał Pawło
 wski\, and will appear in APPROX 2026. \nhttps://arxiv.org/abs/2604.13428
 \n \nThe Oberseminar takes place in the Seminarraum\, 1st floor. Particip
 ants are invited to have coffee or tea in the lounge before.\n \n \n\nht
 tps://math-events.uni-bonn.de/event/1529/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/1529/
END:VEVENT
END:VCALENDAR