Abstract
This work presents an optimally-competitive algorithm for the problem of maximum weighted online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a known set of workers, a distribution over job types, and non-negative utility weights for each pair of worker and job types. At each time step, a job is drawn i.i.d. from the distribution over job types. Upon arrival, the job must be irrevocably assigned to a worker and cannot be dropped. The goal is to maximize the expected sum of utilities after all jobs are assigned.
We introduce Dispatch, a 0.5-competitive, randomized algorithm. We also prove that 0.5-competitive is the best possible. Dispatch first selects a “preferred worker” and assigns the job to this worker if it is available. The preferred worker is determined based on an optimal solution to a fractional transportation problem. If the preferred worker is not available, Dispatch randomly selects a worker from the available workers. We show that Dispatch maintains a uniform distribution over the workers even when the distribution over the job types is non-uniform.
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
Similar content being viewed by others
References
Bansal, N., Buchbinder, N., Gupta, A., Naor, J.S.: An O(log2k)-competitive algorithm for metric bipartite matching. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 522–533. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75520-3_47
Brubach, B., Sankararaman, K.A., Srinivasan, A., Xu, P.: New algorithms, better bounds, and a novel model for online stochastic matching. In: 24th Annual European Symposium on Algorithms, vol. 57, pp. 24:1–24:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016). https://doi.org/10.4230/LIPIcs.ESA.2016.24
Bubeck, S., Cohen, M.B., Lee, Y.T., Lee, J.R., Madry, A.: K-server via multiscale entropic regularization. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 3–16. ACM (2018). https://doi.org/10.1145/3188745.3188798
Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms for a random stream of customers. In: Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 169–186. ACM (2017). https://doi.org/10.1145/3033274.3085137
Dehghani, S., Ehsani, S., Hajiaghayi, M., Liaghat, V., Seddighin, S.: Stochastic k-server: how should uber work? In: 44th International Colloquium on Automata, Languages, and Programming, vol. 80, pp. 126:1–126:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017)
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). https://doi.org/10.1007/978-3-642-10841-9_34
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, pp. 117–126. IEEE (2009). https://doi.org/10.1109/FOCS.2009.72
Haeupler, B., Mirrokni, V.S., Zadimoghaddam, M.: Online stochastic weighted matching: improved approximation algorithms. In: Chen, N., Elkind, E., Koutsoupias, E. (eds.) WINE 2011. LNCS, vol. 7090, pp. 170–181. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25510-6_15
Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478–488 (1993). https://doi.org/10.1006/jagm.1993.1026
Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 352–358. ACM (1990). https://doi.org/10.1145/100216.100262
Kesselheim, T., Radke, K., Tönnis, A., Vöcking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 589–600. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40450-4_50
Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255–267 (1994). https://doi.org/10.1016/0304-3975(94)90042-6
Koutsoupias, E.: The k-server problem. Compu. Sci. Rev. 3(2), 105–118 (2009). https://doi.org/10.1016/j.cosrev.2009.04.002
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). https://doi.org/10.1145/1993636.1993716
Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11(2), 208–230 (1990). https://doi.org/10.1016/0196-6774(90)90003-W
Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: online actions based on offline statistics. Math. Oper. Res. 37(4), 559–573 (2012). https://doi.org/10.1287/moor.1120.0551
Mehta, A., et al.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265–368 (2013). https://doi.org/10.1561/0400000057
Meyerson, A., Nanavati, A., Poplawski, L.: Randomized online algorithms for minimum metric bipartite matching. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 954–959. Society for Industrial and Applied Mathematics (2006)
Raghvendra, S.: A robust and optimal online algorithm for minimum metric bipartite matching. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, vol. 60, pp. 18:1–18:16. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.18
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Chang, M., Hochbaum, D.S., Spaen, Q., Velednitsky, M. (2018). DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals. In: Epstein, L., Erlebach, T. (eds) Approximation and Online Algorithms. WAOA 2018. Lecture Notes in Computer Science(), vol 11312. Springer, Cham. https://doi.org/10.1007/978-3-030-04693-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-04693-4_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04692-7
Online ISBN: 978-3-030-04693-4
eBook Packages: Computer ScienceComputer Science (R0)