TY - GEN
T1 - Optimal algorithms for online b-matching with variable vertex capacities
AU - Albers, Susanne
AU - Schubert, Sebastian
N1 - Publisher Copyright:
© Susanne Albers and Sebastian Schubert; licensed under Creative Commons License CC-BY 4.0
PY - 2021/9/1
Y1 - 2021/9/1
N2 - 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 Ps∈S bs vertices on the left-hand side. From a theoretical point of view our result explores the power of randomization and strictly limits the amount of required randomness. From a practical point of view it leads to more efficient allocation algorithms. Technically, we show that the primal-dual framework of Devanur, Jain and Kleinberg cannot establish a competitiveness better than 1/2 for the original Ranking algorithm, choosing a permutation of the servers. Therefore, we formulate a new configuration LP for the b-matching problem and then conduct a primal-dual analysis. We extend this analysis approach to the vertex-weighted b-matching problem. Specifically, we show that the algorithm PerturbedGreedy by Aggarwal, Goel, Karande and Mehta (SODA 2011), again with a sole randomization over the set of servers, is (1 − 1/e)-competitive. Together with recent work by Huang and Zhang (STOC 2020), our results demonstrate that configuration LPs can be strictly stronger than standard LPs in the analysis of more complex matching problems.
AB - 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 Ps∈S bs vertices on the left-hand side. From a theoretical point of view our result explores the power of randomization and strictly limits the amount of required randomness. From a practical point of view it leads to more efficient allocation algorithms. Technically, we show that the primal-dual framework of Devanur, Jain and Kleinberg cannot establish a competitiveness better than 1/2 for the original Ranking algorithm, choosing a permutation of the servers. Therefore, we formulate a new configuration LP for the b-matching problem and then conduct a primal-dual analysis. We extend this analysis approach to the vertex-weighted b-matching problem. Specifically, we show that the algorithm PerturbedGreedy by Aggarwal, Goel, Karande and Mehta (SODA 2011), again with a sole randomization over the set of servers, is (1 − 1/e)-competitive. Together with recent work by Huang and Zhang (STOC 2020), our results demonstrate that configuration LPs can be strictly stronger than standard LPs in the analysis of more complex matching problems.
KW - B-matching
KW - Configuration LP
KW - Online algorithms
KW - Primal-dual analysis
KW - Unweighted matching
KW - Variable vertex capacities
KW - Vertex-weighted matching
UR - http://www.scopus.com/inward/record.url?scp=85115627698&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs-APPROX/RANDOM.2021.2
DO - 10.4230/LIPIcs-APPROX/RANDOM.2021.2
M3 - Conference contribution
AN - SCOPUS:85115627698
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021
A2 - Wootters, Mary
A2 - Sanita, Laura
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021
Y2 - 16 August 2021 through 18 August 2021
ER -