Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Online Matching: Haste Makes Waste!
event speaker icon
Yuval Emek (IE, Technion)
event date icon
Wednesday, 07.12.2016, 12:30
event location icon
Taub 201
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.