Optimization Online


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

T-H. Hubert Chan(hubert***at***cs.hku.hk)
Fei Chen(fchen***at***cs.hku.hk)
Xiaowei Wu(xwwu***at***cs.hku.hk)

Abstract: 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. 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 non-conventional forms such as the Dirac delta function.

Keywords: Node-weighted oblivious matching problem, Weighted ranking on general graphs, Continuous linear programming

Category 1: Combinatorial Optimization (Graphs and Matroids )


Download: [PDF]

Entry Submitted: 07/08/2014
Entry Accepted: 07/08/2014
Entry Last Modified: 07/08/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society