Document Open Access Logo

Stochastic Online Metric Matching

Authors Anupam Gupta, Guru Guruganesh, Binghui Peng, David Wajc

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.67.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Anupam Gupta
  • Carnegie Mellon University, Pittsburgh, PA, USA
Guru Guruganesh
  • Google Research, United States
Binghui Peng
  • Tsinghua University, China
David Wajc
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Gupta, Anupam: Supported in part by NSF awards CCF-1536002, CCF-1540541, and CCF-1617790, and the Indo-US Joint Center for Algorithms Under Uncertainty.
  • Wajc, David: Supported in part by NSF grants CCF-1618280, CCF-1814603, CCF-1527110, NSF CAREER award CCF-1750808 and a Sloan Research Fellowship.

Cite AsGet BibTex

Anupam Gupta, Guru Guruganesh, Binghui Peng, and David Wajc. Stochastic Online Metric Matching. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.67

Abstract

We study the minimum-cost metric perfect matching problem under online i.i.d arrivals. We are given a fixed metric with a server at each of the points, and then requests arrive online, each drawn independently from a known probability distribution over the points. Each request has to be matched to a free server, with cost equal to the distance. The goal is to minimize the expected total cost of the matching. Such stochastic arrival models have been widely studied for the maximization variants of the online matching problem; however, the only known result for the minimization problem is a tight O(log n)-competitiveness for the random-order arrival model. This is in contrast with the adversarial model, where an optimal competitive ratio of O(log n) has long been conjectured and remains a tantalizing open question. In this paper, we show that the i.i.d model admits substantially better algorithms: our main result is an O((log log log n)^2)-competitive algorithm in this model, implying a strict separation between the i.i.d model and the adversarial and random order models. Along the way we give a 9-competitive algorithm for the line and tree metrics - the first O(1)-competitive algorithm for any non-trivial arrival model for these much-studied metrics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Mathematics of computing → Matchings and factors
Keywords
  • stochastic
  • online
  • online matching
  • metric matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1253-1264, 2011. Google Scholar
  2. Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. A o (n)-Competitive Deterministic Algorithm for Online Matching on a Line. In Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA), pages 11-22, 2014. Google Scholar
  3. Bahman Bahmani and Michael Kapralov. Improved bounds for online stochastic matching. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA), pages 170-181. Springer, 2010. Google Scholar
  4. Nikhil Bansal, Niv Buchbinder, Anupam Gupta, and Joseph Seffi Naor. An O(log² k)-competitive algorithm for metric bipartite matching. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA), pages 522-533, 2007. Google Scholar
  5. Daniel Berend and Aryeh Kontorovich. A sharp estimate of the binomial mean absolute deviation with applications. Statistics &Probability Letters, 83(4):1254-1259, 2013. Google Scholar
  6. Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching. In Proceedings of the 24th Annual European Symposium on Algorithms (ESA), pages 24:1-24:16, 2016. Google Scholar
  7. Minjun Chang, Dorit S Hochbaum, Quico Spaen, and Mark Velednitsky. DISPATCH: an optimally-competitive algorithm for maximum online perfect bipartite matching with iid arrivals. In Proceedings of the 16th Workshop on Approximation and Online Algorithms (WAOA), pages 149-164, 2018. Google Scholar
  8. Ilan Reuven Cohen and David Wajc. Randomized Online Matching in Regular Graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 960-979, 2018. Google Scholar
  9. Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Seddighin. Stochastic k-Server: How Should Uber Work? In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP), pages 126:1-126:14, 2017. Google Scholar
  10. Nikhil R Devanur, Balasubramanian Sivan, and Yossi Azar. Asymptotically optimal algorithm for stochastic adwords. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), pages 388-404, 2012. Google Scholar
  11. Hossein Esfandiari, Nitish Korula, and Vahab S. Mirrokni. Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models. In Proceedings of the 16th ACM Conference on Economics and Computation (EC), pages 169-186, 2015. Google Scholar
  12. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-497, 2004. Google Scholar
  13. Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S Muthukrishnan. Online stochastic matching: Beating 1-1/e. In Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS), pages 117-126, 2009. Google Scholar
  14. Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online Matching with General Arrivals. arXiv preprint arXiv:1904.08255, 2019. Google Scholar
  15. Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online combinatorial optimization problems. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 942-951, 2008. Google Scholar
  16. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 982-991, 2008. Google Scholar
  17. Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh. Set covering with our eyes closed. SIAM Journal on Computing (SICOMP), 42(3):808-830, 2013. Google Scholar
  18. Anupam Gupta and Kevin Lewi. The online metric matching problem for doubling metrics. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP), pages 424-435, 2012. Google Scholar
  19. Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 17-29, 2018. Google Scholar
  20. Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2875-2886, 2019. Google Scholar
  21. Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), pages 1070-1081, 2018. Google Scholar
  22. Bala Kalyanasundaram and Kirk Pruhs. Online weighted matching. Journal of Algorithms, 14(3):478-488, 1993. Google Scholar
  23. Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 587-596, 2011. Google Scholar
  24. Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352-358, 1990. Google Scholar
  25. Samir Khuller, Stephen G Mitchell, and Vijay V Vazirani. On-line algorithms for weighted bipartite matching and stable marriages. Theoretical Computer Science (TCS), 127(2):255-267, 1994. Google Scholar
  26. Mohammad Mahdian, Hamid Nazerzadeh, and Amin Saberi. Allocating online advertisement space with unreliable estimates. In Proceedings of the 8th ACM Conference on Electronic Commerce (EC), pages 288-294, 2007. Google Scholar
  27. Mohammad Mahdian and Qiqi 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), pages 597-606, 2011. Google Scholar
  28. Aranyak Mehta. Online matching and ad allocation. Foundations and Trendsregistered in Theoretical Computer Science, 8(4):265-368, 2013. Google Scholar
  29. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22, 2007. Google Scholar
  30. Adam Meyerson, Akash Nanavati, and Laura Poplawski. Randomized online algorithms for minimum metric bipartite matching. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 954-959, 2006. Google Scholar
  31. Vahab S Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. Simultaneous approximations for adversarial and stochastic online budgeted allocation. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1690-1701, 2012. Google Scholar
  32. Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge university press, 2005. Google Scholar
  33. Joseph Seffi Naor and David Wajc. Near-optimum online ad allocation for targeted advertising. ACM Transactions on Economics and Computation (TEAC), 6(3-4):16, 2018. Google Scholar
  34. Krati Nayyar and Sharath Raghvendra. An input sensitive online algorithm for the metric bipartite matching problem. In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS), pages 505-515, 2017. Google Scholar
  35. Sharath Raghvendra. A robust and optimal online algorithm for minimum metric bipartite matching. In Proceedings of the 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), volume 60, 2016. Google Scholar
  36. Sharath Raghvendra. Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line. In Proceedings of the 34th Symposium on Computational geometry (SoCG), pages 67:1-67:14, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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