License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.4
URN: urn:nbn:de:0030-drops-169420
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16942/
Albers, Susanne ;
Schubert, Sebastian
Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities
Abstract
We study the b-matching problem in bipartite graphs G = (S,R,E). Each vertex s ∈ S is a server with individual capacity b_s. The vertices r ∈ R are requests that arrive online and must be assigned instantly to an eligible server. The goal is to maximize the size of the constructed matching. We assume that G is a (k,d)-graph [J. Naor and D. Wajc, 2018], where k specifies a lower bound on the degree of each server and d is an upper bound on the degree of each request. This setting models matching problems in timely applications.
We present tight upper and lower bounds on the performance of deterministic online algorithms. In particular, we develop a new online algorithm via a primal-dual analysis. The optimal competitive ratio tends to 1, for arbitrary k ≥ d, as the server capacities increase. Hence, nearly optimal solutions can be computed online. Our results also hold for the vertex-weighted problem extension, and thus for AdWords and auction problems in which each bidder issues individual, equally valued bids.
Our bounds improve the previous best competitive ratios. The asymptotic competitiveness of 1 is a significant improvement over the previous factor of 1-1/e^{k/d}, for the interesting range where k/d ≥ 1 is small. Recall that 1-1/e ≈ 0.63. Matching problems that admit a competitive ratio arbitrarily close to 1 are rare. Prior results rely on randomization or probabilistic input models.
BibTeX - Entry
@InProceedings{albers_et_al:LIPIcs.ESA.2022.4,
author = {Albers, Susanne and Schubert, Sebastian},
title = {{Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {4:1--4:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16942},
URN = {urn:nbn:de:0030-drops-169420},
doi = {10.4230/LIPIcs.ESA.2022.4},
annote = {Keywords: online algorithms, deterministic algorithms, primal-dual analysis, b-matching, bounded-degree graph, variable vertex capacities, unweighted matching, vertex-weighted matching}
}
|
Keywords: |
|
online algorithms, deterministic algorithms, primal-dual analysis, b-matching, bounded-degree graph, variable vertex capacities, unweighted matching, vertex-weighted matching |
|
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.09.2022 |
