Universität zu Köln

Eckl, Alexander, Kirschbaum, Anja, Leichter, Marilena ORCID: 0000-0002-1677-4786 and Schewior, Kevin (2021). A stronger impossibility for fully online matching. Oper. Res. Lett., 49 (5). S. 802 - 809. AMSTERDAM: ELSEVIER. ISSN 1872-7468

Full text not available from this repository.

Abstract

We revisit the fully online matching model (Huang et al., 2020), an extension of the classic online matching model due to Karp, Vazirani, and Vazirani (1990), which has recently received a lot of attention (Huang et al., 2019, 2020), partly due to applications in ride-sharing platforms. It has been shown that the fully online version is harder than the classic version for which the achievable competitive ratio is at most 0.6317, rather than precisely 1 - 1/e approximate to 0.6321. We introduce two new ideas to the construction. By optimizing the parameters of the modified construction numerically, we obtain an improved impossibility result of 0.6297. Like the previous bound, the new bound even holds for fractional (rather than randomized) algorithms on bipartite graphs. (C) 2021 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Eckl, Alexander UNSPECIFIED UNSPECIFIED UNSPECIFIED Kirschbaum, Anja UNSPECIFIED UNSPECIFIED UNSPECIFIED Leichter, Marilena UNSPECIFIED orcid.org/0000-0002-1677-4786 UNSPECIFIED Schewior, Kevin UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-570143
DOI:	10.1016/j.orl.2021.08.012
Journal or Publication Title:	Oper. Res. Lett.
Volume:	49
Number:	5
Page Range:	S. 802 - 809
Date:	2021
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1872-7468
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language Operations Research & Management Science Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/57014