Beating Ratio 0.5 for Weighted Oblivious Matching Problems

Authors Melika Abolhassani, T.-H. Hubert Chan, Fei Chen, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Mahini Hamid, Xiaowei Wu



PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.3.pdf
  • Filesize: 0.6 MB
  • 18 pages

Document Identifiers

Author Details

Melika Abolhassani
T.-H. Hubert Chan
Fei Chen
Hossein Esfandiari
MohammadTaghi Hajiaghayi
Mahini Hamid
Xiaowei Wu

Cite AsGet BibTex

Melika Abolhassani, T.-H. Hubert Chan, Fei Chen, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Mahini Hamid, and Xiaowei Wu. Beating Ratio 0.5 for Weighted Oblivious Matching Problems. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.3

Abstract

We prove the first non-trivial performance ratios strictly above 0.5 for weighted versions of the oblivious matching problem. Even for the unweighted version, since Aronson, Dyer, Frieze, and Suen first proved a non-trivial ratio above 0.5 in the mid-1990s, during the next twenty years several attempts have been made to improve this ratio, until Chan, Chen, Wu and Zhao successfully achieved a significant ratio of 0.523 very recently (SODA 2014). To the best of our knowledge, our work is the first in the literature that considers the node-weighted and edge-weighted versions of the problem in arbitrary graphs (as opposed to bipartite graphs). (1) For arbitrary node weights, we prove that a weighted version of the Ranking algorithm has ratio strictly above 0.5. We have discovered a new structural property of the ranking algorithm: if a node has two unmatched neighbors at the end of algorithm, then it will still be matched even when its rank is demoted to the bottom. This property allows us to form LP constraints for both the node-weighted and the unweighted oblivious matching problems. As a result, we prove that the ratio for the node-weighted case is at least 0.501512. Interestingly via the structural property, we can also improve slightly the ratio for the unweighted case to 0.526823 (from the previous best 0.523166 in SODA 2014). (2) For a bounded number of distinct edge weights, we show that ratio strictly above 0.5 can be achieved by partitioning edges carefully according to the weights, and running the (unweighted) Ranking algorithm on each part. Our analysis is based on a new primal-dual framework known as \emph{matching coverage}, in which dual feasibility is bypassed. Instead, only dual constraints corresponding to edges in an optimal matching are satisfied. Using this framework we also design and analyze an algorithm for the edge-weighted online bipartite matching problem with free disposal. We prove that for the case of bounded online degrees, the ratio is strictly above 0.5.
Keywords
  • Weighted matching
  • oblivious algorithms
  • Ranking
  • linear programming

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 2011, San Francisco, California, USA, January 23-25, 2011, pages 1253-1264, 2011. Google Scholar
  2. Jonathan Aronson, Martin Dyer, Alan Frieze, and Stephen Suen. Randomized greedy matching. ii. Random Struct. Algorithms, 6(1):55-73, January 1995. URL: http://dx.doi.org/10.1002/rsa.3240060107.
  3. Benjamin Birnbaum and Claire Mathieu. On-line bipartite matching made simple. SIGACT News, 39(1):80-87, March 2008. URL: http://dx.doi.org/10.1145/1360443.1360462.
  4. Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA, pages 253-264, 2007. Google Scholar
  5. T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, and Zhichao Zhao. Ranking on arbitrary graphs: Rematch via continuous lp with monotone and boundary condition constraints. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1112-1122, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.82.
  6. 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 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 101-107, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.7.
  7. Martin E. Dyer and Alan M. Frieze. Randomized greedy matching. Random Struct. Algorithms, 2(1):29-46, 1991. URL: http://dx.doi.org/10.1002/rsa.3240020104.
  8. Jon Feldman, Nitish Korula, Vahab S. Mirrokni, S. Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. In Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings., pages 374-385, 2009. URL: http://dx.doi.org/10.1007/978-3-642-10841-9_34.
  9. 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 2008, San Francisco, California, USA, January 20-22, 2008, pages 982-991, 2008. Google Scholar
  10. Gagan Goel and Pushkar Tripathi. Matching with our eyes closed. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 718-727, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.19.
  11. Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 587-596, 2011. URL: http://dx.doi.org/10.1145/1993636.1993715.
  12. 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. URL: http://dx.doi.org/10.1145/100216.100262.
  13. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 597-606, 2011. URL: http://dx.doi.org/10.1145/1993636.1993716.
  14. Silvio Micali and Vijay V. Vazirani. An O(√V E) algorithm for finding maximum matching in general graphs. In FOCS'80, pages 17-27. IEEE Computer Society, 1980. URL: http://dx.doi.org/10.1109/SFCS.1980.12.
  15. Alvin E Roth, Tayfun Sönmez, and M Utku Ünver. Pairwise kidney exchange. Journal of Economic theory, 125(2):151-188, 2005. 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