Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity

Chan, THH; Chen, F; Wu, XW

Chan, THH (reprint author), Univ Hong Kong, Dept Comp Sci, Pokfulam Rd, Hong Kong, Hong Kong, Peoples R China.

ACM TRANSACTIONS ON ALGORITHMS, 2018; 14 (2):

Abstract

We prove the first non-trivial performance ratio strictly above 0.5 for the weighted Ranking algoritlun on the oblivious matching problem where nodes ......

Full Text Link