{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T04:13:24Z","timestamp":1751602404340,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,16]],"date-time":"2018-04-16T00:00:00Z","timestamp":1523836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["17200214"],"award-info":[{"award-number":["17200214"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>We prove the first non-trivial performance ratio strictly above 0.5 for the weighted Ranking algorithm on the oblivious matching problem where nodes in a general graph can have arbitrary weights.<\/jats:p><jats:p>We have discovered a new structural property of the ranking algorithm: if a node has two unmatched neighbors, 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 weighted and the unweighted versions of the problem.<\/jats:p><jats:p>Using a new class of continuous linear programming (LP), we prove that the ratio for the weighted case is at least 0.501512, and we improve the ratio for the unweighted case to 0.526823 (from the previous best 0.523166 in SODA 2014). Unlike previous continuous LP, in which the primal solution must be continuous everywhere, our new continuous LP framework allows the monotone component of the primal function to have jump discontinuities, and the other primal components to take non-conventional forms, such as the Dirac \u03b4 function.<\/jats:p>","DOI":"10.1145\/3168008","type":"journal-article","created":{"date-parts":[[2018,4,18]],"date-time":"2018-04-18T17:21:50Z","timestamp":1524072110000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity"],"prefix":"10.1145","volume":"14","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fei","family":"Chen","sequence":"additional","affiliation":[{"name":"Huawei Noah\u2019s Ark Lab, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaowei","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Gagan Aggarwal Gagan Goel Chinmay Karande and Aranyak Mehta. 2011. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceeedings of SODA. 1253--1264. Gagan Aggarwal Gagan Goel Chinmay Karande and Aranyak Mehta. 2011. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceeedings of SODA. 1253--1264.","DOI":"10.1137\/1.9781611973082.95"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060107"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"T.-H. Hubert Chan Fei Chen Xiaowei Wu and Zhichao Zhao. 2014. Ranking on arbitrary graphs: Rematch via continuous LP with monotone and boundary condition constraints. In Proceeedings of SODA. 1112--1122. T.-H. Hubert Chan Fei Chen Xiaowei Wu and Zhichao Zhao. 2014. Ranking on arbitrary graphs: Rematch via continuous LP with monotone and boundary condition constraints. In Proceeedings of SODA. 1112--1122.","DOI":"10.1137\/1.9781611973402.82"},{"volume-title":"Kleinberg","year":"2013","author":"Devanur Nikhil R.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020104"},{"key":"e_1_2_1_6_1","unstructured":"Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to Adwords. In Proceeedings of SODA. 982--991. Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to Adwords. In Proceeedings of SODA. 982--991."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.19"},{"volume-title":"Matching with our eyes closed. CoRR abs\/1306.2988","year":"2013","author":"Goel Gagan","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993715"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90187-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.20"},{"volume-title":"Pairwise Kidney Exchange. Working Paper 10698","author":"Roth Alvin E.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0113043"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3168008","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3168008","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T19:26:21Z","timestamp":1751570781000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3168008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,16]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3168008"],"URL":"https:\/\/doi.org\/10.1145\/3168008","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,4,16]]},"assertion":[{"value":"2016-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}