File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Beating ratio 0.5 for weighted oblivious matching problems

TitleBeating ratio 0.5 for weighted oblivious matching problems
Authors
KeywordsWeighted matching
Oblivious algorithms
Ranking
Linear programming
Issue Date2016
PublisherESA.
Citation
The 24rd Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 22-26 August 2016. In Conference Proceedings, 2016, p. 48:1-48:16 How to Cite?
AbstractWe prove the first non-trivial 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 non-trivial ratio above 0.5 in the mid-1990s, 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 node-weighted and edge-weighted 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 node-weighted and the unweighted oblivious matching problems. As a result, we prove that the ratio for the node-weighted 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 primal-dual 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 edge-weighted online bipartite matching problem with free disposal. We prove that for the case of bounded online degrees, the ratio is strictly above 0.5.
DescriptionESA 2016 is organized in collaboration with the European Association for Theoretical Computer Science (EATCS) and is a part of ALGO 2016
Persistent Identifierhttp://hdl.handle.net/10722/232176

 

DC FieldValueLanguage
dc.contributor.authorAbolhassani, M-
dc.contributor.authorChan, HTH-
dc.contributor.authorChen, F-
dc.contributor.authorEsfandiari, H-
dc.contributor.authorHajiaghayi, M-
dc.contributor.authorMahini, H-
dc.contributor.authorWu, X-
dc.date.accessioned2016-09-20T05:28:15Z-
dc.date.available2016-09-20T05:28:15Z-
dc.date.issued2016-
dc.identifier.citationThe 24rd Annual European Symposium on Algorithms (ESA 2016), Aarhus, Denmark, 22-26 August 2016. In Conference Proceedings, 2016, p. 48:1-48:16-
dc.identifier.urihttp://hdl.handle.net/10722/232176-
dc.descriptionESA 2016 is organized in collaboration with the European Association for Theoretical Computer Science (EATCS) and is a part of ALGO 2016-
dc.description.abstractWe prove the first non-trivial 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 non-trivial ratio above 0.5 in the mid-1990s, 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 node-weighted and edge-weighted 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 node-weighted and the unweighted oblivious matching problems. As a result, we prove that the ratio for the node-weighted 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 primal-dual 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 edge-weighted 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.languageeng-
dc.publisherESA.-
dc.relation.ispartofEuropean Symposium on Algorithms, ESA 2016 Proceedings-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsAuthor holds the copyright-
dc.subjectWeighted matching-
dc.subjectOblivious algorithms-
dc.subjectRanking-
dc.subjectLinear programming-
dc.titleBeating ratio 0.5 for weighted oblivious matching problems-
dc.typeConference_Paper-
dc.identifier.emailChan, HTH: hubert@cs.hku.hk-
dc.identifier.emailChen, F: feier@hku.hk-
dc.identifier.emailWu, X: wxw0711@hku.hk-
dc.identifier.authorityChan, HTH=rp01312-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.4230/LIPIcs.ESA.2016.48-
dc.identifier.hkuros264466-
dc.identifier.spage48:1-
dc.identifier.epage48:16-
dc.customcontrol.immutablesml 161116-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats