Abstract

Traditional online algorithms deal typically with (1) inputs over a sequence with a goal of minimizing the total cost; (2) inputs over a time where the goal is to minimize some function of the time. Following the work of Emek, Kutten and Wattenhofer (STOC'16) we consider problems where the goal is to minimize the cost plus the waiting time (delay) until requests are served. In particular we deal with online min-cost matching with delays (matching players in game platforms) and online two sided min-cost matching with delays (matching customers to drivers in transportation platforms such as Uber/Lyft). We provide logarithmic competitive algorithms for these problems.

Based on joint work with Chiplunkar, Kaplan (SODA’ 17), Ashlagi, Charikar, Chiplunkar, Geri, Kaplan, Makhijani, Wang, Wattenhofer (APPROX’ 17).