Document Open Access Logo

Min-Cost Bipartite Perfect Matching with Delays

Authors Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, Roger Wattenhofer

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.1.pdf
  • Filesize: 0.54 MB
  • 20 pages

Document Identifiers

Author Details

Itai Ashlagi
Yossi Azar
Moses Charikar
Ashish Chiplunkar
Ofir Geri
Haim Kaplan
Rahul Makhijani
Yuyi Wang
Roger Wattenhofer

Cite As Get BibTex

Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, and Roger Wattenhofer. Min-Cost Bipartite Perfect Matching with Delays. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.1

Abstract

In the min-cost bipartite perfect matching with delays (MBPMD) problem, requests arrive online at points of a finite metric space. Each request is either positive or negative and has to be matched to a request of opposite polarity. As opposed to traditional online matching problems, the algorithm does not have to serve requests as they arrive, and may choose to match them later at a cost. Our objective is to minimize the sum of the distances between matched pairs of requests (the connection cost) and the sum of the waiting times of the requests (the delay cost). This objective exhibits a natural tradeoff between minimizing the distances and the cost of waiting for better matches. This tradeoff appears in many real-life scenarios, notably, ride-sharing platforms. MBPMD is related to its non-bipartite variant, min-cost perfect matching with delays (MPMD), in which each request can be matched to any other request. MPMD was introduced by Emek et al. (STOC'16), who showed an O(log^2(n)+log(Delta))-competitive randomized algorithm on n-point metric spaces with aspect ratio Delta.

Our contribution is threefold. First, we present a new lower bound construction for MPMD and MBPMD. We get a lower bound of Omega(sqrt(log(n)/log(log(n)))) on the competitive ratio of any randomized algorithm for MBPMD. For MPMD, we improve the lower bound from Omega(sqrt(log(n))) (shown by Azar et al., SODA'17) to Omega(log(n)/log(log(n))), thus, almost matching their upper bound of O(log(n)). Second, we adapt the algorithm of Emek et al. to the bipartite case, and provide a simplified analysis that improves the competitive ratio to O(log(n)). The key ingredient of the algorithm is an O(h)-competitive randomized algorithm for MBPMD on weighted trees of height h. Third, we provide an O(h)-competitive deterministic algorithm for MBPMD on weighted trees of height h. This algorithm is obtained by adapting the algorithm for MPMD by Azar et al. to the apparently more complicated bipartite setting.

Subject Classification

Keywords
  • online algorithms with delayed service
  • bipartite matching
  • competitive analysis

Metrics

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

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 Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1253-1264, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.95.
  2. Mohammad Akbarpour, Shengwu Li, and Shayan Oveis Gharan. Thickness and information in dynamic matching markets. Available at SSRN 2394319, 2017. Google Scholar
  3. Ross Anderson, Itai Ashlagi, David Gamarnik, and Yash Kanoria. A dynamic model of barter exchange. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1925-1933, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.129.
  4. Itai Ashlagi, Maximilien Burq, Patrick Jaillet, and Vahideh H. Manshadi. On matching and thickness in heterogeneous dynamic markets. In Proceedings of the 2016 ACM Conference on Economics and Computation, page 765, 2016. URL: http://dx.doi.org/10.1145/2940716.2940758.
  5. Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Polylogarithmic bounds on the competitiveness of min-cost perfect matching with delays. In Proceedings of the Twenty-eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1051-1061, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.67.
  6. Mariagiovanna Baccara, SangMok Lee, and Leeat Yariv. Optimal dynamic matching. Available at SSRN 2641670, 2015. Google Scholar
  7. Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic-competitive algorithm for the k-server problem. J. ACM, 62(5):40, 2015. URL: http://dx.doi.org/10.1145/2783434.
  8. Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 184-193, 1996. URL: http://dx.doi.org/10.1109/SFCS.1996.548477.
  9. Yair Bartal. Graph decomposition lemmas and their role in metric embedding methods. In Proceedings of the Twelfth Annual European Symposium on Algorithms, pages 89-97, 2004. URL: http://dx.doi.org/10.1007/978-3-540-30140-0_10.
  10. Allan Borodin and Ran El-Yaniv. On randomization in on-line computation. Inf. Comput., 150(2):244-267, 1999. URL: http://dx.doi.org/10.1006/inco.1998.2775.
  11. 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, pages 101-107, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.7.
  12. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online matching: haste makes waste! In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 333-344, 2016. URL: http://dx.doi.org/10.1145/2897518.2897557.
  13. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online matching: Haste makes waste!, 2016. arXiv:1603.03024 [cs.DS]. URL: http://arxiv.org/abs/1603.03024.
  14. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. URL: http://dx.doi.org/10.1016/j.jcss.2004.04.011.
  15. 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, pages 352-358, 1990. URL: http://dx.doi.org/10.1145/100216.100262.
  16. Aranyak Mehta. Online matching and ad allocation. Found. Trends Theor. Comput. Sci., 8(4):265-368, October 2013. URL: http://dx.doi.org/10.1561/0400000057.
  17. Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. Adwords and generalized online matching. J. ACM, 54(5), 2007. URL: http://dx.doi.org/10.1145/1284320.1284321.
  18. Leen Stougie and Arjen P. A. Vestjens. Randomized algorithms for on-line scheduling problems: how low can't you go? Oper. Res. Lett., 30(2):89-96, 2002. URL: http://dx.doi.org/10.1016/S0167-6377(01)00115-8.
  19. Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, pages 222-227, 1977. URL: http://dx.doi.org/10.1109/SFCS.1977.24.
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 About DROPS Imprint Privacy Contact