Abstract
We consider the generalizations of two classical problems, online bipartite matching and ski rental, in the field of online algorithms, and establish a novel connection between them.
In the original setting of online bipartite matching, vertices from only one side of the bipartite graph are online. Motivated by market clearing applications where both buyers and sellers are online, we study the generalization, called two-sided online bipartite matching, in which all vertices can be online. An algorithm for it should maintain a \(b\)-matching and try to maximize its size. We show that this problem can be attacked by considering the complementary “dual” problem, two-sided online bipartite vertex cover, which in fact is a generalization of ski rental.
As the greedy algorithm is 1/2-competitive for both problems, the challenge is to beat the ratio of 1/2. In this paper, we present new 0.526-competitive algorithms for both problems under the large budget assumption. A key technical ingredient of our results is a charging-based framework for the design and analysis of water-filling type algorithms. This allows us to systematically establish approximation bounds for various water-filling algorithms.
On the hardness side, we show that no online randomized algorithm achieves a competitive ratio better than 0.570 and 0.625 respectively for these two problems. Our bounds show that the one-sided optimal ratio of \(1-1/e\approx 0.632\) is indeed unattainable.
S.C-W. Wong—This research was supported by NSF grants CCF0964033 and CCF1408635, and by Templeton Foundation grant 3966.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM (2011)
Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When LP is the cure for your matching woes: improved bounds for stochastic matchings. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part II. LNCS, vol. 6347, pp. 218–229. Springer, Heidelberg (2010)
Birnbaum, B., Mathieu, C.: On-line bipartite matching made simple. ACM SIGACT News 39(1), 80–87 (2008)
Blum, A., Sandholm, T., Zinkevich, M.: Online algorithms for market clearing. Journal of the ACM (JACM) 53(5), 845–879 (2006)
Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 253–264. Springer, Heidelberg (2007)
Demange, M., Paschos, V.T.: On-line vertex-covering. Theoretical Computer Science 332(1), 83–108 (2005)
Devanur, N.R., Huang, Z., Korula, N., Mirrokni, V.S., Yan, Q.: Whole-page optimization and submodular welfare maximization with online bidders. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 305–322. ACM (2013)
Devanur, N.R., Jain, K.: Online matching with concave returns. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 137–144. ACM (2012)
Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of ranking for online bipartite matching. In: SODA 2013: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (to appear, 2013)
Devenur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: EC 2009: Proceedings of the Tenth ACM Conference on Electronic Commerce, pp. 71–78. ACM, New York (2009)
Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., Pál, M.: Online ad assignment with free disposal. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 374–385. Springer, Heidelberg (2009)
Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: Beating 1–1/e. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 117–126. IEEE (2009)
Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: SODA, vol. 8, pp. 982–991 (2008)
Kalyanasundaram, B., Pruhs, K.R.: An optimal deterministic algorithm for online b-matching. Theoretical Computer Science 233(1), 319–325 (2000)
Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 587–596. ACM (2011)
Karlin, A.R., Kenyon, C., Randall, D.: Dynamic tcp acknowledgement and other stories about e/(e-1). In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 502–509. ACM (2001)
Karlin, A.R., Manasse, M.S., McGeoch, L.A., Owicki, S.: Competitive randomized algorithms for nonuniform problems. Algorithmica 11(6), 542–571 (1994)
Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3(1), 79–119 (1988)
Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 352–358. ACM(1990)
Lotker, Z., Patt-Shamir, B., Rawitz, D., Albers, S.: Rent, lease or buy: Randomized algorithms for multislope ski rental. In: 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), vol. 1 (2008)
Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 597–606. ACM (2011)
Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: Online actions based on offline statistics. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1285–1294. SIAM (2011)
Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. Journal of the ACM (JACM) 54(5), 22 (2007)
Mehta, A.: Online matching and ad allocation. Theoretical Computer Science 8(4), 265–368 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, Y., Wong, S.Cw. (2015). Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_87
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_87
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)