Impatient Online Matching

Authors Xingwu Liu, Zhida Pan, Yuyi Wang, Roger Wattenhofer



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.62.pdf
  • Filesize: 0.57 MB
  • 12 pages

Document Identifiers

Author Details

Xingwu Liu
  • SKL Computer Architecture, ICT, CAS , University of Chinese Academy of Sciences, Beijing, China
Zhida Pan
  • Institute of Computing Technology, Chinese Academy of Sciences, University of Chinese Academy of Sciences, Beijing, China
Yuyi Wang
  • ETH Zurich, Switzerland
Roger Wattenhofer
  • ETH Zurich, Switzerland

Cite AsGet BibTex

Xingwu Liu, Zhida Pan, Yuyi Wang, and Roger Wattenhofer. Impatient Online Matching. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 62:1-62:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.62

Abstract

We investigate the problem of Min-cost Perfect Matching with Delays (MPMD) in which requests are pairwise matched in an online fashion with the objective to minimize the sum of space cost and time cost. Though linear-MPMD (i.e., time cost is linear in delay) has been thoroughly studied in the literature, it does not well model impatient requests that are common in practice. Thus, we propose convex-MPMD where time cost functions are convex, capturing the situation where time cost increases faster and faster. Since the existing algorithms for linear-MPMD are not competitive any more, we devise a new deterministic algorithm for convex-MPMD problems. For a large class of convex time cost functions, our algorithm achieves a competitive ratio of O(k) on any k-point uniform metric space. Moreover, our deterministic algorithm is asymptotically optimal, which uncover a substantial difference between convex-MPMD and linear-MPMD which allows a deterministic algorithm with constant competitive ratio on any uniform metric space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online algorithm
  • online matching
  • convex function
  • competitive analysis
  • lower bound

Metrics

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

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, SODA, page 1253–1264, 2011. Google Scholar
  2. 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 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Berkeley, California, USA, August 2017. Google Scholar
  3. Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays. arXiv, 2016. URL: http://arxiv.org/abs/1610.05155.
  4. 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, SODA, page 1051–1061, 2017. Google Scholar
  5. Yossi Azar, Arun Ganesh, Rong Ge, and Debmalya Panigrahi. Online service with delay. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 551-563. ACM, 2017. Google Scholar
  6. Benjamin E. Birnbaum and Claire Mathieu. On-line bipartite matching made simple. SIGACT News, 39(1):80–87, 2008. Google Scholar
  7. 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, page 101–107, 2013. Google Scholar
  8. Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of Research of the National Bureau of Standards B, 69:125–130, 1965. Google Scholar
  9. Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965. Google Scholar
  10. Yuval Emek, Shay Kutten, and Roger Wattenhofer. Online Matching: Haste makes Waste! In 48th Annual Symposium on Theory of Computing (STOC), June 2016. Google Scholar
  11. Yuval Emek, Yaacov Shapiro, and Yuyi Wang. Minimum Cost Perfect Matching with Delays for Two Sources. In 10th International Conference on Algorithms and Complexity (CIAC), Athens, Greece, May 2017. Google Scholar
  12. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to Adwords. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, page 982–991, 2008. Google Scholar
  13. Bala Kalyanasundaram and Kirk Pruhs. Online Weighted Matching. J. Algorithms, 14(3):478–488, 1993. Google Scholar
  14. 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
  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, page 352–358, 1990. Google Scholar
  16. Samir Khuller, Stephen G. Mitchell, and Vijay V. Vazirani. On-Line Algorithms for Weighted Bipartite Matching and Stable Marriages. Theor. Comput. Sci., 127(2):255–267, 1994. Google Scholar
  17. Aranyak Mehta. Online Matching and Ad Allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013. Google Scholar
  18. Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. AdWords and Generalized On-line Matching. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), page 264–273, 2005. Google Scholar
  19. Adam Meyerson, Akash Nanavati, and Laura J. Poplawski. Randomized online algorithms for minimum metric bipartite matching. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2006. Google Scholar
  20. Shuichi Miyazaki. On the advice complexity of online bipartite matching and online stable marriage. Inf. Process. Lett., 114(12):714–717, 2014. Google Scholar
  21. Joseph Naor and David Wajc. Near-Optimum Online Ad Allocation for Targeted Advertising. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC, page 131–148, 2015. 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