Supplementary

Citations:
 Appears in Collections:
Conference Paper: Beating ratio 0.5 for weighted oblivious matching problems
Title  Beating ratio 0.5 for weighted oblivious matching problems 

Authors  
Keywords  Weighted matching Oblivious algorithms Ranking Linear programming 
Issue Date  2016 
Publisher  ESA. 
Citation  The 24rd Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2226 August 2016. In Conference Proceedings, 2016, p. 48:148:16 How to Cite? 
Abstract  We prove the first nontrivial 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 nontrivial ratio above 0.5 in the mid1990s, 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 nodeweighted and edgeweighted 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 nodeweighted and the unweighted oblivious matching problems. As a result, we prove that the ratio for the nodeweighted 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 primaldual framework known as 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 edgeweighted online bipartite matching problem with free disposal. We prove that for the case of bounded online degrees, the ratio is strictly above 0.5. 
Description  ESA 2016 is organized in collaboration with the European Association for Theoretical Computer Science (EATCS) and is a part of ALGO 2016 
Persistent Identifier  http://hdl.handle.net/10722/232176 
DC Field  Value  Language 

dc.contributor.author  Abolhassani, M   
dc.contributor.author  Chan, HTH   
dc.contributor.author  Chen, F   
dc.contributor.author  Esfandiari, H   
dc.contributor.author  Hajiaghayi, M   
dc.contributor.author  Mahini, H   
dc.contributor.author  Wu, X   
dc.date.accessioned  20160920T05:28:15Z   
dc.date.available  20160920T05:28:15Z   
dc.date.issued  2016   
dc.identifier.citation  The 24rd Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 2226 August 2016. In Conference Proceedings, 2016, p. 48:148:16   
dc.identifier.uri  http://hdl.handle.net/10722/232176   
dc.description  ESA 2016 is organized in collaboration with the European Association for Theoretical Computer Science (EATCS) and is a part of ALGO 2016   
dc.description.abstract  We prove the first nontrivial 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 nontrivial ratio above 0.5 in the mid1990s, 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 nodeweighted and edgeweighted 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 nodeweighted and the unweighted oblivious matching problems. As a result, we prove that the ratio for the nodeweighted 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 primaldual framework known as 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 edgeweighted online bipartite matching problem with free disposal. We prove that for the case of bounded online degrees, the ratio is strictly above 0.5.   
dc.language  eng   
dc.publisher  ESA.   
dc.relation.ispartof  European Symposium on Algorithms, ESA 2016 Proceedings   
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.rights  Author holds the copyright   
dc.subject  Weighted matching   
dc.subject  Oblivious algorithms   
dc.subject  Ranking   
dc.subject  Linear programming   
dc.title  Beating ratio 0.5 for weighted oblivious matching problems   
dc.type  Conference_Paper   
dc.identifier.email  Chan, HTH: hubert@cs.hku.hk   
dc.identifier.email  Chen, F: feier@hku.hk   
dc.identifier.email  Wu, X: wxw0711@hku.hk   
dc.identifier.authority  Chan, HTH=rp01312   
dc.description.nature  published_or_final_version   
dc.identifier.doi  10.4230/LIPIcs.ESA.2016.48   
dc.identifier.hkuros  264466   
dc.identifier.spage  48:1   
dc.identifier.epage  48:16   
dc.customcontrol.immutable  sml 161116   