The Taub Faculty of Computer Science Events and Talks

We address a new online problem, referred to as min-cost perfect matching with delays (MPMD), where requests arrive in a continuous time online fashion at the points of a finite metric space $mathcal{M}$ and should be served by matching them to each other.

The algorithm that knows $mathcal{M}$ in advance is allowed to delay its matching commitments, but this does not come for free: the total cost of the algorithm is the sum of metric distances between matched requests plus the sum of times each request waited since it arrived until it was matched.

In this talk, we discuss the MPMD problem, its applications, and some recent advances in studying its competitiveness.

The talk will be self contained.