Journal
ACM EC '19: PROCEEDINGS OF THE 2019 ACM CONFERENCE ON ECONOMICS AND COMPUTATION
Volume -, Issue -, Pages 729-742Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3328526.3329573
Keywords
Online Matching; Online Windowed Matching; Carpooling; Ride sharing; Kidney Exchange; Batching
Funding
- Office of Naval Research [N00014-15-1-2083, N00014-18 -1-2122]
Ask authors/readers for more resources
Motivated by applications from ride-sharing and kidney exchange, we study the problem of matching agents who arrive at a marketplace over time and leave after d time periods. Agents can only be matched while they are present in the marketplace. Each pair of agents can yield a different match value, and the planner's goal is to maximize the total value over a finite time horizon. First we study the case in which vertices arrive in an adversarial order. We provide a randomized 1/4-competitive algorithm building on a result by Feldman et al. [14] and Lehmann et al. [23]. We extend the model to the case in which departure times are drawn independently from a distribution with non-decreasing hazard rate, for which we establish a 1/8-competitive algorithm. When the arrival order is chosen uniformly at random, we show that a batching algorithm, which computes a maximum-weighted matching every (d + 1) periods, is 0.279-competitive.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available