Document Open Access Logo

Secretary Matching Meets Probing with Commitment

Authors Allan Borodin, Calum MacRury, Akash Rakheja

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.13.pdf
  • Filesize: 0.82 MB
  • 23 pages

Document Identifiers

Author Details

Allan Borodin
  • Department of Computer Science, University of Toronto, Canada
Calum MacRury
  • Department of Computer Science, University of Toronto, Canada
Akash Rakheja
  • Department of Computer Science, University of Toronto, Canada

Acknowledgements

We would like to thank Denis Pankratov, Rajan Udwani, and David Wajc for their very constructive comments on this paper.

Cite AsGet BibTex

Allan Borodin, Calum MacRury, and Akash Rakheja. Secretary Matching Meets Probing with Commitment. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.13

Abstract

We consider the online bipartite matching problem within the context of stochastic probing with commitment. This is the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching. We consider the competitiveness of online algorithms in the adversarial order model (AOM) and the secretary/random order model (ROM). More specifically, we consider an unknown bipartite stochastic graph G = (U,V,E) where U is the known set of offline vertices, V is the set of online vertices, G has edge probabilities (p_{e})_{e ∈ E}, and G has edge weights (w_{e})_{e ∈ E} or vertex weights (w_u)_{u ∈ U}. Additionally, G has a downward-closed set of probing constraints (𝒞_{v})_{v ∈ V}, where 𝒞_v indicates which sequences of edges adjacent to an online vertex v can be probed. This model generalizes the various settings of the classical bipartite matching problem (i.e. with and without probing). Our contributions include the introduction and analysis of probing within the random order model, and our generalization of probing constraints which includes budget (i.e. knapsack) constraints. Our algorithms run in polynomial time assuming access to a membership oracle for each 𝒞_v. In the vertex weighted setting, for adversarial order arrivals, we generalize the known 1/2 competitive ratio to our setting of 𝒞_v constraints. For random order arrivals, we show that the same algorithm attains an asymptotic competitive ratio of 1-1/e, provided the edge probabilities vanish to 0 sufficiently fast. We also obtain a strict competitive ratio for non-vanishing edge probabilities when the probing constraints are sufficiently simple. For example, if each 𝒞_v corresponds to a patience constraint 𝓁_v (i.e., 𝓁_v is the maximum number of probes of edges adjacent to v), and any one of following three conditions is satisfied (each studied in previous papers), then there is a conceptually simple greedy algorithm whose competitive ratio is 1-1/e. - When the offline vertices are unweighted. - When the online vertex probabilities are "vertex uniform"; i.e., p_{u,v} = p_v for all (u,v) ∈ E. - When the patience constraint 𝓁_v satisfies 𝓁_v ∈ {[1,|U|} for every online vertex; i.e., every online vertex either has unit or full patience. Finally, in the edge weighted case, we match the known optimal 1/e asymptotic competitive ratio for the classic (i.e. without probing) secretary matching problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Stochastic probing
  • Online algorithms
  • Bipartite matching
  • Optimization under uncertainty

Metrics

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

Related Versions

References

  1. Marek Adamczyk. Improved analysis of the greedy algorithm for stochastic matching. Inf. Process. Lett., 111(15):731-737, 2011. Google Scholar
  2. Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi, and Michal Wlodarczyk. When the optimum is also blind: a new perspective on universal optimization. In ICALP, 2017. Google Scholar
  3. Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee. Improved approximation algorithms for stochastic matching. CoRR, abs/1505.01439, 2015. URL: http://arxiv.org/abs/1505.01439.
  4. Allan Borodin, Calum MacRury, and Akash Rakheja. Greedy approaches to online stochastic matching. CoRR, abs/2008.09260, 2020. URL: https://arxiv.org/abs/2008.09260.
  5. Allan Borodin, Calum MacRury, and Akash Rakheja. Prophet inequality matching meets probing with commitment. CoRR, abs/2102.04325, 2021. URL: https://arxiv.org/abs/2102.04325.
  6. Brian Brubach, Nathaniel Grammel, Will Ma, and Aravind Srinivasan. Follow your star: New frameworks for online stochastic matching with known and unknown patience. CoRR, abs/1907.03963, 2021. Google Scholar
  7. Brian Brubach, Nathaniel Grammel, Will Ma, and Aravind Srinivasan. Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. CoRR, abs/2106.06892, 2021. URL: http://arxiv.org/abs/2106.06892.
  8. Brian Brubach, Nathaniel Grammel, and Aravind Srinivasan. Vertex-weighted online stochastic matching with patience constraints. 2019, 1907.03963, 2019. URL: http://arxiv.org/abs/1907.03963.
  9. Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra. Approximating matches made in heaven. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, ICALP '09, pages 266-278, 2009. Google Scholar
  10. Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, pages 101-107, Philadelphia, PA, USA, 2013. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=2627817.2627824.
  11. Bernd Gärtner and Jirí Matousek. Understanding and using linear programming. Universitext. Springer, 2007. Google Scholar
  12. Vineet Goyal and R. Udwani. Online matching with stochastic rewards: Optimal competitive ratio via path based formulation. Proceedings of the 21st ACM Conference on Economics and Computation, 2020. Google Scholar
  13. Nathaniel Grammel, Brian Brubach, Will Ma, and Aravind Srinivasan. Follow your star: New frameworks for online stochastic matching with known and unknown patience. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, pages 2872-2880, 2021. Google Scholar
  14. Anupam Gupta and Viswanath Nagarajan. A stochastic probing problem with applications. In Michel X. Goemans and José R. Correa, editors, Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings, volume 7801 of Lecture Notes in Computer Science, pages 205-216. Springer, 2013. Google Scholar
  15. Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals, 2018. URL: http://arxiv.org/abs/1804.07458.
  16. Zhiyi Huang and Qiankun Zhang. Online primal dual meets online matching with stochastic rewards: Configuration lp to the rescue. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 1153–1164, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3357713.3384294.
  17. 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, May 13-17, 1990, Baltimore, Maryland, USA, pages 352-358, 1990. Google Scholar
  18. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms - ESA 2013, pages 589-600, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  19. Euiwoong Lee and Sahil Singla. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1-57:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.57.
  20. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing lps. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC '11, pages 597-606, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993636.1993716.
  21. Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res., 37(4):559-573, 2012. Google Scholar
  22. Aranyak Mehta and Debmalya Panigrahi. Online matching with stochastic rewards. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 728-737. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.65.
  23. Aranyak Mehta, Bo Waggoner, and Morteza Zadimoghaddam. Online stochastic matching with unequal probabilities. In SODA, pages 1388-1404, 2015. Google Scholar
  24. Manish Purohit, Sreenivas Gollapudi, and Manish Raghavan. Hiring under uncertainty. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5181-5189. PMLR, June 09-15 2019. Google Scholar
  25. Rebecca Reiffenhäuser. An optimal truthful mechanism for the online weighted bipartite matching problem. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1982-1993. SIAM, 2019. Google Scholar
  26. D. Seese. Groetschel, m., l. lovasz, a. schrijver: Geometric algorithms and combinatorial optimization. (algorithms and combinatorics. eds.: R. l. graham, b. korte, l. lovasz. vol. 2), springer-verlag 1988, xii, 362 pp., 23 figs., dm 148,-. isbn 3–540–13624-x. Biometrical Journal, 32(8):930-930, 1990. URL: https://doi.org/10.1002/bimj.4710320805.
  27. Jan Vondrák, Chandra Chekuri, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, page 783–792, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1993636.1993740.
  28. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, USA, 1st edition, 2011. 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