Top

Theory of Computing Systems

Published in:

07-09-2019

An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals

Authors: Minjun Chang, Dorit S. Hochbaum, Quico Spaen, Mark Velednitsky

Published in: Theory of Computing Systems | Issue 4/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present an optimally-competitive algorithm for the problem of maximum 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. When a job arrives, 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.

previous article Approximating Node-Weighted k-MST on Planar Graphs

next article Longest Increasing Subsequence under Persistent Comparison Errors

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Agatz, N., Erera, A., Savelsbergh, M., Wang, X.: Optimization for dynamic ride-sharing: A review. Eur. J. Oper. Res. 223(2), 295–303 (2012)CrossRef

Aksin, Z., Armony, M., Mehrotra, V.: The modern call center: A multi-disciplinary perspective on operations management research. Prod. Oper. Manag. 16(6), 665–688 (2007)CrossRef

Bansal, N., Buchbinder, N., Gupta, A., Naor, J. S.: An \(O(\log ^{2} k)\)-competitive algorithm for metric bipartite matching. In: European symposium on algorithms. pp. 522–533. Springer (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: International workshop on internet and network economics. pp. 374–385. Springer (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

10.

Haeupler, B., Mirrokni, V. S., Zadimoghaddam, M.: Online stochastic weighted matching: Improved approximation algorithms. In: International workshop on internet and network economics. pp. 170–181. Springer (2011), https://doi.org/10.1007/978-3-642-25510-6_15

11.

Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478–488 (1993). https://doi.org/10.1006/jagm.1993.1026 MathSciNetCrossRefMATH

12.

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

13.

Kesselheim, T., Radke, K., Tönnis, A., Vöcking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: European symposium on algorithms. pp. 589–600. Springer (2013), https://doi.org/10.1007/978-3-642-40450-4_50

14.

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 MathSciNetCrossRefMATH

15.

Koutsoupias, E.: The k-server problem. Comput. Sci. Rev. 3(2), 105–118 (2009). https://doi.org/10.1016/j.cosrev.2009.04.002 CrossRefMATH

16.

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

17.

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 MathSciNetCrossRefMATH

18.

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 MathSciNetCrossRefMATH

19.

Mehta, A., et al.: Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science 8(4), 265–368 (2013). https://doi.org/10.1561/0400000057 MathSciNetCrossRefMATH

20.

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)

21.

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

22.

Ross, S. M.: Introduction to probability models. Academic press (2014)

23.

Su, X., Zenios, S. A.: Patient choice in kidney allocation: A sequential stochastic assignment model. Oper. Res. 53(3), 443–455 (2005)MathSciNetCrossRef

Title: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals
Authors: Minjun Chang
Dorit S. Hochbaum
Quico Spaen
Mark Velednitsky
Publication date: 07-09-2019
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 4/2020
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-019-09947-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2020

Correction to: Special Issue on Approximation and Online Algorithms

Longest Increasing Subsequence under Persistent Comparison Errors

Special Issue on Approximation and Online Algorithms

Approximating Node-Weighted k-MST on Planar Graphs

Deterministic Min-Cost Matching with Delays

Advice Complexity of Priority Algorithms

Premium Partner