Abstract | ||
---|---|---|
We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) introduced by Emek et al. (STOC 2016). In this problem, an even number of requests appear in a metric space at different times and the goal of an online algorithm is to match them in pairs. In contrast to traditional online matching problems, in MPMD all requests appear online and an algorithm can match any pair of requests, but such decision may be delayed (e.g., to find a better match). The cost is the sum of matching distances and the introduced delays. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/978-3-319-89441-6_11 | WAOA |
DocType | Volume | Citations |
Conference | abs/1704.06980 | 0 |
PageRank | References | Authors |
0.34 | 40 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marcin Bienkowski | 1 | 254 | 27.18 |
Artur Kraska | 2 | 0 | 0.68 |
Pawel Schmidt | 3 | 0 | 1.01 |