World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Online Matching in Regular Bipartite Graphs

    In an online problem, the input is revealed one piece at a time. In every time step, the online algorithm has to produce a part of the output, based on the partial knowledge of the input. Such decisions are irrevocable, and thus online algorithms usually lead to nonoptimal solutions. The impact of the partial knowledge depends strongly on the problem. If the algorithm is allowed to read binary information about the future, the amount of bits read that allow the algorithm to solve the problem optimally is the so-called advice complexity. The quality of an online algorithm is measured by its competitive ratio, which compares its performance to that of an optimal offline algorithm.

    In this paper we study online bipartite matchings focusing on the particular case of bipartite matchings in regular graphs. We give tight upper and lower bounds on the competitive ratio of the online deterministic bipartite matching problem. The competitive ratio turns out to be asymptotically equal to the known randomized competitive ratio. Afterwards, we present an upper and lower bound for the advice complexity of the online deterministic bipartite matching problem.

    References

    • 1. A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis (Cambridge University Press, 1998). Google Scholar
    • 2. D. Komm, An Introduction to Online Computation (Springer, 2016). CrossrefGoogle Scholar
    • 3. 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) (1990), pp. 352–358. Google Scholar
    • 4. A. Mehta, A. Saberi, U. V. Vazirani and V. V. Vazirani, AdWords and generalized online matching, Journal of the ACM 54(5) :1–19 (2007). Crossref, ISIGoogle Scholar
    • 5. A. Meyerson, A. Nanavati and L. Poplawski, Randomized online algorithms for minimum metric bipartite matching, in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006), pp. 954–959. Google Scholar
    • 6. B. Kalyanasundaram and K. Pruhs, Online weighted matching, Journal of Algorithms 14(3) :478–488 (1993). Crossref, ISIGoogle Scholar
    • 7. B. Fuchs, W. Hochstättler and W. Kern, Online matching on a line, Electronic Notes in Discrete Mathematics 13 :49–51 (2003). CrossrefGoogle Scholar
    • 8. K. Chaudhuri, C. Daskalakis, R. D. Kleinberg and H. Lin, Online bipartite perfect matching with augmentations, in Proceedings of IEEE INFOCOM (2009), pp. 1044–1052. Google Scholar
    • 9. B. Birnbaum and C. Mathieu, On-line bipartite matching made simple, ACM SIGACT News 39(1):80 (2008). Google Scholar
    • 10. M. Mahdian and Q. Yan, 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 (STOC) (2011), pp. 597–605. Google Scholar
    • 11. J. Feldman, A. Mehta, V. Mirrokni and S. Muthukrishnan, Online stochastic matching: Beating 1 1/e, in Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2009), pp. 117–126. Google Scholar
    • 12. J. Naor and D. Wajc, Near-optimum online Ad allocation for targeted advertising, in Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC’15) (2015), pp. 131–148. Google Scholar
    • 13. R. Diestel, Graph Theory, 3rd edn. (Springer, 2005). Google Scholar
    • 14. S. Dobrev, R. Královič and D. Pardubská, How much information about the future is needed?, SOFSEM 2008: Theory and Practice of Computer Science, Lecture Notes in Computer Science, Vol. 4910 (2008), pp. 247–258. CrossrefGoogle Scholar
    • 15. Y. Emek, P. Fraigniaud, A. Korman and A. Rosén, Online computation with advice, Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, Vol. 5555 (2009), pp. 427–438. CrossrefGoogle Scholar
    • 16. H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič and T. Mömke, On the advice complexity of online problems, Algorithms and Computation (ISAAC 2009), Lecture Notes in Computer Science, Vol. 5878 (2009), pp. 331–340. CrossrefGoogle Scholar
    • 17. S. Miyazaki, On the advice complexity of online bipartite matching and online stable marriage, Information Processing Letters 114(12) :714–717 (2014). Crossref, ISIGoogle Scholar