Edge-Weighted Online Windowed Matching

Itai Ashlagi (), Maximilien Burq (), Chinmoy Dutta (), Patrick Jaillet (), Amin Saberi () and Chris Sholley ()
Additional contact information
Itai Ashlagi: Management Science and Engineering Department, Stanford University, Stanford, California 94305
Maximilien Burq: Verily Life Sciences LLC, South San Francisco, California 94080
Chinmoy Dutta: Turing Research Inc., Mountain View, California 94040
Patrick Jaillet: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Amin Saberi: Management Science and Engineering Department, Stanford University, Stanford, California 94305
Chris Sholley: Lyft, San Francisco, California 94107

Mathematics of Operations Research, 2023, vol. 48, issue 2, 999-1016

Abstract: 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 1 / 4 -competitive algorithm. When departure times are drawn independently from a distribution with nondecreasing hazard rate, we establish a 1 / 8 -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.

Keywords: Primary: 68W27; secondary: 68W20; 68W40; 68Q25; online matching algorithms; edge-weighted online matching; nonbipartite matching; windowed matching; adversarial arrivals; random order arrivals; batching (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1289 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:2:p:999-1016

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().