2026-07-21T23:20:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16942 2024-03-06T10:58:46Z ddc:004 open_access

Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities Albers, Susanne Schubert, Sebastian online algorithms deterministic algorithms primal-dual analysis b-matching bounded-degree graph variable vertex capacities unweighted matching vertex-weighted matching 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Susanne Albers and Sebastian Schubert 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.4 urn:nbn:de:0030-drops-169420 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.4 eng https://creativecommons.org/licenses/by/4.0/legalcode