Document Open Access Logo

Semi-Online Bipartite Matching

Authors Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, Erik Vee

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2019.50.pdf
  • Filesize: 0.54 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Semi-Online Algorithms
  • Bipartite Matching

Metrics

Abstract

In this paper we introduce the semi-online model that generalizes the classical online computational model. The semi-online model postulates that the unknown future has a predictable part and an adversarial part; these parts can be arbitrarily interleaved. An algorithm in this model operates as in the standard online model, i.e., makes an irrevocable decision at each step.
We consider bipartite matching in the semi-online model. Our main contributions are competitive algorithms for this problem and a near-matching hardness bound. The competitive ratio of the algorithms nicely interpolates between the truly offline setting (i.e., no adversarial part) and the truly online setting (i.e., no predictable part).

Cite As Get BibTex

Ravi Kumar, Manish Purohit, Aaron Schild, Zoya Svitkina, and Erik Vee. Semi-Online Bipartite Matching. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.50

Author Details

Ravi Kumar
  • Google, Mountain View, CA, USA
Manish Purohit
  • Google, Mountain View, CA, USA
Aaron Schild
  • University of California, Berkeley, CA, USA
Zoya Svitkina
  • Google, Mountain View, CA, USA
Erik Vee
  • Google, Mountain View, CA, USA

References

  1. S. Albers and M Hellwig. Semi-online scheduling revisited. Theor. Comput. Sci., 443:1-9, 2012. Google Scholar
  2. J. Balogh and J Békési. Semi-on-line bin packing: a short overview and a new lower bound. Cent. Eur. J. Oper. Res., 21(4):685-698, 2013. Google Scholar
  3. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic, Richard Královic, and Tobias Mömke. On the Advice Complexity of Online Problems. In ISAAC, pages 331-340, 2009. Google Scholar
  4. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 2005. Google Scholar
  5. Sebastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In COLT, pages 42.1-42.23, 2012. Google Scholar
  6. Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM (JACM), 53(3):324-360, 2006. Google Scholar
  7. Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and streaming complexity of maximum bipartite matching. In SODA, pages 468-485. Society for Industrial and Applied Mathematics, 2012. Google Scholar
  8. Pascal Van Hentenryck and Russell Bent. Online stochastic combinatorial optimization. The MIT Press, 2009. Google Scholar
  9. Bala Kalyanasundaram and Kirk Pruhs. An optimal deterministic algorithm for online b-matching. Theor. Comput. Sci., 233(1-2):319-325, 2000. URL: http://dx.doi.org/10.1016/S0304-3975(99)00140-1.
  10. Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In STOC, pages 587-596, 2011. Google Scholar
  11. Anna R. Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP Acknowledgment and Other Stories about e/(e-1). Algorithmica, 36(3):209-224, 2003. Google Scholar
  12. Anna R. Karlin, Mark S. Manasse, Lyle A. McGeoch, and Susan Owicki. Competitive randomized algorithms for nonuniform problems. Algorithmica, 11(6):542-571, 1994. Google Scholar
  13. Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In STOC, pages 352-358, 1990. Google Scholar
  14. Ravi Kumar, Manish Purohit, and Zoya Svitkina. Improving Online Algorithms Using ML Predictions. In NIPS, 2018. Google Scholar
  15. Euiwoong Lee and Sahil Singla. Maximum Matching in the Online Batch-Arrival Model. In IPCO, pages 355-367, 2017. Google Scholar
  16. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In ICML, pages 3302-3311, 2018. Google Scholar
  17. Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Online optimization with uncertain information. ACM Trans. Algorithms, 8(1):2:1-2:29, 2012. Google Scholar
  18. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In STOC, pages 597-606, 2011. Google Scholar
  19. Andres Muñoz Medina and Sergei Vassilvitskii. Revenue Optimization with Approximate Bid Predictions. In NIPS, pages 1856-1864, 2017. Google Scholar
  20. Aranyak Mehta. Online Matching and Ad Allocation. Foundations and Trendsregistered in Theoretical Computer Science, 8(4):265-368, 2013. Google Scholar
  21. Vahab S. Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Simultaneous approximations for adversarial and stochastic online budgeted allocation. In SODA, pages 1690-1701, 2012. Google Scholar
  22. Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram. Optimal online assignment with forecasts. In EC, pages 109-118, 2010. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact