Optimal Algorithms for Online b-Matching with Variable Vertex Capacities

Susanne Albers, Sebastian Schubert

Research output: Contribution to journalArticlepeer-review

Abstract

We study the b-matching problem, which generalizes classical online matching introduced by Karp, Vazirani and Vazirani (STOC 1990). Consider a bipartite graph G=(S∪˙R,E). Every vertex s∈S is a server with a capacity bs, indicating the number of possible matching partners. The vertices r∈R are requests that arrive online and must be matched immediately to an eligible server. The goal is to maximize the cardinality of the constructed matching. In contrast to earlier work, we study the general setting where servers may have arbitrary, individual capacities. We prove that the most natural and simple online algorithms achieve optimal competitive ratios. As for deterministic algorithms, we give a greedy algorithm RelativeBalance and analyze it by extending the primal-dual framework of Devanur, Jain and Kleinberg (SODA 2013). In the area of randomized algorithms we study the celebrated Ranking algorithm by Karp, Vazirani and Vazirani. We prove that the original Ranking strategy, simply picking a random permutation of the servers, achieves an optimal competitiveness of 1-1/e, independently of the server capacities. Hence it is not necessary to resort to a reduction, replacing every server s by bs vertices of unit capacity and to then run Ranking on this graph with ∑s∈Sbs vertices on the left-hand side. Additionally, we extend this result to the vertex-weighted b-matching problem. Technically, we formulate a new configuration LP for the b-matching problem and conduct a primal-dual analysis.

Original languageEnglish
JournalAlgorithmica
DOIs
StateAccepted/In press - 2024

Keywords

  • b-matching
  • Configuration LP
  • Online algorithms
  • Primal-dual analysis
  • unweighted matching
  • variable vertex capacities
  • vertex-weighted matching

Fingerprint

Dive into the research topics of 'Optimal Algorithms for Online b-Matching with Variable Vertex Capacities'. Together they form a unique fingerprint.

Cite this