Edge-Weighted Online Windowed Matching
| Autor: | Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, Chris Sholley |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Mathematics of Operations Research. 48:999-1016 |
| ISSN: | 1526-5471 0364-765X |
| DOI: | 10.1287/moor.2022.1289 |
| Popis: | Consider a matching problem, in which agents arrive to a marketplace over time and leave after some time periods. Agents can only be matched while present in the marketplace. Each pair of agents can yield a different match value, and a social planner seeks to maximize the total value from matches over a finite time horizon. First we study the case in which vertices arrive in an adversarial order. For the case when agents depart in the order of arrival, we provide a randomized [Formula: see text]-competitive algorithm. When departure times are drawn independently from a distribution with nondecreasing hazard rate, we establish a [Formula: see text]-competitive algorithm. When the arrival order is chosen uniformly at random and agents leave after a fixed number of time periods, a batching algorithm, which computes a maximum-weighted matching periodically, is shown to be 0.279-competitive. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|