Optimal Algorithms for Online b-Matching with Variable Vertex Capacities

Authors Susanne Albers, Sebastian Schubert



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.2.pdf
  • Filesize: 0.75 MB
  • 18 pages

Document Identifiers

Author Details

Susanne Albers
  • Department of Computer Science, Technische Universität München, Germany
Sebastian Schubert
  • Department of Computer Science, Technische Universität München, Germany

Cite AsGet BibTex

Susanne Albers and Sebastian Schubert. Optimal Algorithms for Online b-Matching with Variable Vertex Capacities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.2

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 b_s, 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 b_s vertices of unit capacity and to then run Ranking on this graph with ∑_{s ∈ S} b_s 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • primal-dual analysis
  • configuration LP
  • b-matching
  • variable vertex capacities
  • unweighted matching
  • vertex-weighted matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. G. Aggarwal, G. Goel, C. Karande, and A. Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1253-1264. SIAM, 2011. Google Scholar
  2. Y. Azar and A. Litichevskey. Maximizing throughput in multi-queue switches. Algorithmica, 45(1):69-90, 2006. Google Scholar
  3. B.E. Birnbaum and C. Mathieu. On-line bipartite matching made simple. SIGACT News, 39(1):80-87, 2008. Google Scholar
  4. N. Buchbinder, K. Jain, and J. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science, pages 253-264. Springer, 2007. Google Scholar
  5. K. Chaudhuri, C. Daskalakis, R.D. Kleinberg, and H. Lin. Online bipartite perfect matching with augmentations. In Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM), pages 1044-1052, 2009. Google Scholar
  6. N.R. Devanur, K. Jain, and R.D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 101-107, 2013. Google Scholar
  7. A. Eden, M. Feldman, A. Fiat, and K. Segal. An economics-based analysis of RANKING for online bipartite matching. In Proceedings of the 4th Symposium on Simplicity in Algorithms (SOSA), pages 107-110, 2021. Google Scholar
  8. G. Goel and A. Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the 19thAnnual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 982-991, 2008. Google Scholar
  9. E.F. Grove, M.-Y. Kao, P. Krishnan, and J.S. Vitter. Online perfect matching and mobile computing. In Proceedings 4th International Workshop, on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 194-205. Springer, 1995. Google Scholar
  10. Z. Huang and Q. Zhang. Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1153-1164, 2020. Google Scholar
  11. Z. Huang, Q. Zhang, and Y. Zhang. Adwords in a panorama. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1416-1426, 2020. Google Scholar
  12. B. Jin and D.P. Williamson. Improved analysis of RANKING for online vertex-weighted bipartite matching. CoRR, abs/2007.12823, 2020. URL: http://arxiv.org/abs/2007.12823.
  13. B. Kalyanasundaram and K. Pruhs. An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci., 233(1-2):319-325, 2000. Google Scholar
  14. C. Karande, A. Mehta, and P. Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 587-596. ACM, 2011. Google Scholar
  15. R.M. Karp, U.V. Vazirani, and V.V. Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352-358, 1990. Google Scholar
  16. M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pages 597-606, 2011. Google Scholar
  17. A. Mehta and D. Panigrahi. Online matching with stochastic rewards. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 728-737, 2012. Google Scholar
  18. A. Mehta, A. Saberi, U.V. Vazirani, and V.V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5):22, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail