{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T09:53:21Z","timestamp":1748512401096,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"German Research Foundation \u2013 Research Training Group AdONE","award":["277991500"],"award-info":[{"award-number":["277991500"]}]},{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,2]]},"abstract":"Abstract<\/jats:title>\n We study the b<\/jats:italic>-matching problem, which generalizes classical online matching introduced by Karp, Vazirani and Vazirani (STOC 1990). Consider a bipartite graph \n \n $$G=(S\\dot{\\cup }R,E)$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n S<\/mml:mi>\n \n \u222a<\/mml:mo>\n \u02d9<\/mml:mo>\n <\/mml:mover>\n R<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Every vertex \n \n $$s\\in S$$<\/jats:tex-math>\n \n \n s<\/mml:mi>\n \u2208<\/mml:mo>\n S<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is a server with a capacity \n \n $$b_s$$<\/jats:tex-math>\n \n \n b<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, indicating the number of possible matching partners. The vertices \n \n $$r\\in R$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n \u2208<\/mml:mo>\n R<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> 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<\/jats:sc> 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<\/jats:sc> algorithm by Karp, Vazirani and Vazirani. We prove that the original Ranking<\/jats:sc> strategy, simply picking a random permutation of the servers, achieves an optimal competitiveness of \n \n $$1-1\/e$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n -<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n e<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, independently of the server capacities. Hence it is not necessary to resort to a reduction, replacing every server s<\/jats:italic> by \n \n $$b_s$$<\/jats:tex-math>\n \n \n b<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> vertices of unit capacity and to then run Ranking<\/jats:sc> on this graph with \n \n $$\\sum _{s\\in S} b_s$$<\/jats:tex-math>\n \n \n \n \u2211<\/mml:mo>\n \n s<\/mml:mi>\n \u2208<\/mml:mo>\n S<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n b<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> vertices on the left-hand side. Additionally, we extend this result to the vertex-weighted b<\/jats:italic>-matching problem. Technically, we formulate a new configuration LP for the b<\/jats:italic>-matching problem and conduct a primal-dual analysis.<\/jats:p>","DOI":"10.1007\/s00453-024-01282-9","type":"journal-article","created":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T07:19:48Z","timestamp":1731050388000},"page":"167-190","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Algorithms for Online b-Matching with Variable Vertex Capacities"],"prefix":"10.1007","volume":"87","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Schubert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"key":"1282_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1253\u20131264. SIAM, (2011)","DOI":"10.1137\/1.9781611973082.95"},{"key":"1282_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity - A Modern Approach. Cambridge University Press, (2009)","DOI":"10.1017\/CBO9780511804090"},{"issue":"1","key":"1282_CR3","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00453-005-1190-x","volume":"45","author":"Y Azar","year":"2006","unstructured":"Azar, Y., Litichevskey, A.: Maximizing throughput in multi-queue switches. Algorithmica 45(1), 69\u201390 (2006)","journal-title":"Algorithmica"},{"key":"1282_CR4","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Holm, J., Rotenberg, E.:Online bipartite matching with amortized O(log $$ ^{\\text{2}}$$n) replacements. J. ACM, 66(5):37:1\u201337:23 (2019)","DOI":"10.1145\/3344999"},{"issue":"1","key":"1282_CR5","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/1360443.1360462","volume":"39","author":"BE Birnbaum","year":"2008","unstructured":"Birnbaum, B.E., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80\u201387 (2008)","journal-title":"SIGACT News"},{"key":"1282_CR6","doi-asserted-by":"crossref","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online bipartite matching in offline time. In Proc. 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 384\u2013393, (2014)","DOI":"10.1109\/FOCS.2014.48"},{"key":"1282_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Jain, K., Naor, J.: Online primal-dual algorithms for maximizing ad-auctions revenue. In Proc. 15th Annual European Symposium on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science, pages 253\u2013264. Springer, (2007)","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"1282_CR8","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J., Wajc, D.: Lossless online rounding for online bipartite matching (despite its impossibility). In Proc. 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2030\u20132068. SIAM, (2023)","DOI":"10.1137\/1.9781611977554.ch78"},{"key":"1282_CR9","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Daskalakis, C., Kleinberg, R.D., Lin, H.: Online bipartite perfect matching with augmentations. In Proc. 28th IEEE International Conference on Computer Communications (INFOCOM), pages 1044\u20131052, (2009)","DOI":"10.1109\/INFCOM.2009.5062016"},{"key":"1282_CR10","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of RANKING for online bipartite matching. In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 101\u2013107, (2013)","DOI":"10.1137\/1.9781611973105.7"},{"key":"1282_CR11","unstructured":"D\u00fcrr, C., Konrad, C., Renault, M.: On the power of advice and randomization for online bipartite matching. In Proc. 24th Annual European Symposium on Algorithms (ESA), volume\u00a057 of LIPIcs, pages 37:1\u201337:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2016)"},{"key":"1282_CR12","doi-asserted-by":"crossref","unstructured":"Eden, A., Feldman, M., Fiat, A., Segal, K.: An economics-based analysis of RANKING for online bipartite matching. In Proc. 4th Symposium on Simplicity in Algorithms (SOSA), pages 107\u2013110, (2021)","DOI":"10.1137\/1.9781611976496.12"},{"key":"1282_CR13","doi-asserted-by":"crossref","unstructured":"Gamlath, B., Kapralov, M., Maggiori, A., Svensson, O., Wajc, D.: Online matching with general arrivals. In Proc. 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 26\u201337, (2019)","DOI":"10.1109\/FOCS.2019.00011"},{"key":"1282_CR14","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to Adwords. In Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 982\u2013991, (2008)"},{"issue":"2","key":"1282_CR15","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1287\/opre.2022.2345","volume":"71","author":"V Goyal","year":"2023","unstructured":"Goyal, V., Udwani, R.: Online matching with stochastic rewards: Optimal competitive ratio via path-based formulation. Oper. Res. 71(2), 563\u2013580 (2023)","journal-title":"Oper. Res."},{"key":"1282_CR16","doi-asserted-by":"crossref","unstructured":"Grove, E.F., Kao, M.-Y., Krishnan, P., Vitter, J.S.: Online perfect matching and mobile computing. In Proc. 4th International Workshop, on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 194\u2013205. Springer, (1995)","DOI":"10.1007\/3-540-60220-8_62"},{"key":"1282_CR17","unstructured":"Huang, Z., Tr\u00f6bst, T.: Applications of online matching. In F.\u00a0Echenique, N.\u00a0Immorlica, and V.V. Vazirani, editors, Online and Matching-Based Market Design, pages 109\u2013129. Cambridge University Press, (2023)"},{"key":"1282_CR18","doi-asserted-by":"crossref","unstructured":"Huang Z., Zhang, Q.: Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue. In Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1153\u20131164, (2020)","DOI":"10.1145\/3357713.3384294"},{"key":"1282_CR19","doi-asserted-by":"crossref","unstructured":"Huang, Z., Zhang, Q., Zhang, Y.: Adwords in a panorama. In Proc. 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1416\u20131426, (2020)","DOI":"10.1109\/FOCS46700.2020.00133"},{"key":"1282_CR20","doi-asserted-by":"crossref","unstructured":"Jin, B., Williamson, D.P.: Improved analysis of RANKING for online vertex-weighted bipartite matching. In Proc. 17th International Conference on Web and Internet Economics (WINE), volume 13112 of Lecture Notes in Computer Science, pages 207\u2013225. Springer, (2021)","DOI":"10.1007\/978-3-030-94676-0_12"},{"issue":"1\u20132","key":"1282_CR21","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(99)00140-1","volume":"233","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci. 233(1\u20132), 319\u2013325 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"1282_CR22","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In Proc. 43rd ACM Symposium on Theory of Computing (STOC), pages 587\u2013596. ACM, (2011)","DOI":"10.1145\/1993636.1993715"},{"key":"1282_CR23","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352\u2013358, (1990)","DOI":"10.1145\/100216.100262"},{"key":"1282_CR24","unstructured":"Liang, J., Tang, Z.G., Xu, Y.E., Zhang, Y., Zhou, R.: On the perturbation function of Ranking and Balance for weighted online bipartite matching. In Proc. 31st Annual European Symposium on Algorithms (ESA), volume 274 of LIPIcs, pages 80:1\u201380:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2023)"},{"key":"1282_CR25","doi-asserted-by":"crossref","unstructured":"Mahdian M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In Proc. 43rd ACM Symposium on Theory of Computing (STOC), pages 597\u2013606, (2011)","DOI":"10.1145\/1993636.1993716"},{"issue":"4","key":"1282_CR26","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2013","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265\u2013368 (2013)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"1282_CR27","doi-asserted-by":"crossref","unstructured":"Mehta, A., Panigrahi, D.: Online matching with stochastic rewards. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 728\u2013737, (2012)","DOI":"10.1109\/FOCS.2012.65"},{"issue":"5","key":"1282_CR28","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1284320.1284321","volume":"54","author":"A Mehta","year":"2007","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized online matching. J. ACM 54(5), 22 (2007)","journal-title":"J. ACM"},{"key":"1282_CR29","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, (2005)","DOI":"10.1017\/CBO9780511813603"},{"key":"1282_CR30","doi-asserted-by":"crossref","unstructured":"Motwani R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, (1995)","DOI":"10.1017\/CBO9780511814075"},{"key":"1282_CR31","doi-asserted-by":"crossref","unstructured":"Udwani, R.: Adwords with unknown budgets and beyond. In Proc. 24th ACM Conference on Economics and Computation (EC), page 1128. ACM, to appear in Management Science, (2023)","DOI":"10.1145\/3580507.3597724"},{"key":"1282_CR32","unstructured":"Vazirani, V.V.: Randomized online algorithms for Adwords. CoRR, abs\/2107.10777, (2021)"},{"key":"1282_CR33","unstructured":"Vazirani, V.V.: Towards a practical, budget-oblivious algorithm for the Adwords problem under small bids. In Proc. 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 284 of LIPIcs, pages 21:1\u201321:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2023)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01282-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01282-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01282-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T13:39:06Z","timestamp":1739367546000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01282-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["1282"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01282-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"3 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Susanne Albers has received support from the German Research Foundation - Research Training Group AdONE (GRK2201, 277991500). Other than that, the authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}