File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Edge-Weighted Online Bipartite Matching

TitleEdge-Weighted Online Bipartite Matching
Authors
KeywordsFactor-revealing linear program
free disposal
online bipartite matching
online correlated selection
primal-dual method
Issue Date17-Nov-2022
PublisherAssociation for Computing Machinery (ACM)
Citation
Journal of the ACM, 2022, v. 69, n. 6 How to Cite?
Abstract

Online bipartite matching is one of the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) gave an elegant algorithm for unweighted bipartite matching that achieves an optimal competitive ratio of 1 - 1/e. Aggarwal et al. (SODA 2011) later generalized their algorithm and analysis to the vertex-weighted case. Little is known, however, about the most general edge-weighted problem aside from the trivial 1/2-competitive greedy algorithm. In this article, we present the first online algorithm that breaks the long-standing 1/2 barrier and achieves a competitive ratio of at least 0.5086. In light of the hardness result of Kapralov, Post, and Vondrak (SODA 2013), which restricts beating a 1/2 competitive ratio for the more general monotone submodular welfare maximization problem, our result can be seen as strong evidence that edge-weighted bipartite matching is strictly easier than submodular welfare maximization in an online setting.

The main ingredient in our online matching algorithm is a novel subroutine called online correlated selection (OCS), which takes a sequence of pairs of vertices as input and selects one vertex from each pair. Instead of using a fresh random bit to choose a vertex from each pair, the OCS negatively correlates decisions across different pairs and provides a quantitative measure on the level of correlation. We believe our OCS technique is of independent interest and will find further applications in other online optimization problems.


Persistent Identifierhttp://hdl.handle.net/10722/331153
ISSN
2023 Impact Factor: 2.3
2023 SCImago Journal Rankings: 2.866
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorFahrbach, M-
dc.contributor.authorHuang, Z-
dc.contributor.authorTao, R-
dc.contributor.authorZadimoghaddam, M-
dc.date.accessioned2023-09-21T06:53:12Z-
dc.date.available2023-09-21T06:53:12Z-
dc.date.issued2022-11-17-
dc.identifier.citationJournal of the ACM, 2022, v. 69, n. 6-
dc.identifier.issn0004-5411-
dc.identifier.urihttp://hdl.handle.net/10722/331153-
dc.description.abstract<p>Online bipartite matching is one of the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) gave an elegant algorithm for unweighted bipartite matching that achieves an optimal competitive ratio of 1 - 1/e. Aggarwal et al. (SODA 2011) later generalized their algorithm and analysis to the vertex-weighted case. Little is known, however, about the most general edge-weighted problem aside from the trivial 1/2-competitive greedy algorithm. In this article, we present the first online algorithm that breaks the long-standing 1/2 barrier and achieves a competitive ratio of at least 0.5086. In light of the hardness result of Kapralov, Post, and Vondrak (SODA 2013), which restricts beating a 1/2 competitive ratio for the more general monotone submodular welfare maximization problem, our result can be seen as strong evidence that edge-weighted bipartite matching is strictly easier than submodular welfare maximization in an online setting.</p><p>The main ingredient in our online matching algorithm is a novel subroutine called online correlated selection (OCS), which takes a sequence of pairs of vertices as input and selects one vertex from each pair. Instead of using a fresh random bit to choose a vertex from each pair, the OCS negatively correlates decisions across different pairs and provides a quantitative measure on the level of correlation. We believe our OCS technique is of independent interest and will find further applications in other online optimization problems.</p>-
dc.languageeng-
dc.publisherAssociation for Computing Machinery (ACM)-
dc.relation.ispartofJournal of the ACM-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectFactor-revealing linear program-
dc.subjectfree disposal-
dc.subjectonline bipartite matching-
dc.subjectonline correlated selection-
dc.subjectprimal-dual method-
dc.titleEdge-Weighted Online Bipartite Matching-
dc.typeArticle-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1145/3556971-
dc.identifier.scopuseid_2-s2.0-85146369311-
dc.identifier.volume69-
dc.identifier.issue6-
dc.identifier.eissn1557-735X-
dc.identifier.isiWOS:000891615200007-
dc.identifier.issnl0004-5411-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats