  


Analyzing NodeWeighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity
TH. Hubert Chan(hubertcs.hku.hk) Abstract: We prove the first nontrivial 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. 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. Using a new class of continuous LP, we prove that the ratio for the weighted case is at least 0.501512, and 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 nonconventional forms such as the Dirac delta function. Keywords: Nodeweighted oblivious matching problem, Weighted ranking on general graphs, Continuous linear programming Category 1: Combinatorial Optimization (Graphs and Matroids ) Citation: Download: [PDF] Entry Submitted: 07/08/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  