Online bipartite matching with decomposable weights
Charikar M, Henzinger MH, Nguyễn HL. 2014. Online bipartite matching with decomposable weights. 22nd Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LNCS, vol. 8737, 260–271.
Download (ext.)
https://arxiv.org/abs/1409.2139
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Charikar, Moses;
Henzinger, MonikaISTA ;
Nguyễn, Huy L.
Series Title
LNCS
Abstract
We study a weighted online bipartite matching problem: G(V 1, V 2, E) is a weighted bipartite graph where V 1 is known beforehand and the vertices of V 2 arrive online. The goal is to match vertices of V 2 as they arrive to vertices in V 1, so as to maximize the sum of weights of edges in the matching. If assignments to V 1 cannot be changed, no bounded competitive ratio is achievable. We study the weighted online matching problem with free disposal, where vertices in V 1 can be assigned multiple times, but only get credit for the maximum weight edge assigned to them over the course of the algorithm. For this problem, the greedy algorithm is 0.5-competitive and determining whether a better competitive ratio is achievable is a well known open problem.
We identify an interesting special case where the edge weights are decomposable as the product of two factors, one corresponding to each end point of the edge. This is analogous to the well studied related machines model in the scheduling literature, although the objective functions are different. For this case of decomposable edge weights, we design a 0.5664 competitive randomized algorithm in complete bipartite graphs. We show that such instances with decomposable weights are non-trivial by establishing upper bounds of 0.618 for deterministic and 0.8 for randomized algorithms.
A tight competitive ratio of 1 − 1/e ≈ 0.632 was known previously for both the 0-1 case as well as the case where edge weights depend on the offline vertices only, but for these cases, reassignments cannot change the quality of the solution. Beating 0.5 for weighted matching where reassignments are necessary has been a significant challenge. We thus give the first online algorithm with competitive ratio strictly better than 0.5 for a non-trivial case of weighted matching with free disposal.
Publishing Year
Date Published
2014-09-01
Proceedings Title
22nd Annual European Symposium on Algorithms
Publisher
Springer Nature
Volume
8737
Page
260 - 271
Conference
ESA: Annual European Symposium on Algorithms
Conference Location
Wroclaw, Poland
Conference Date
2014-09-08 – 2014-09-10
ISBN
ISSN
IST-REx-ID
Cite this
Charikar M, Henzinger MH, Nguyễn HL. Online bipartite matching with decomposable weights. In: 22nd Annual European Symposium on Algorithms. Vol 8737. Springer Nature; 2014:260-271. doi:10.1007/978-3-662-44777-2_22
Charikar, M., Henzinger, M. H., & Nguyễn, H. L. (2014). Online bipartite matching with decomposable weights. In 22nd Annual European Symposium on Algorithms (Vol. 8737, pp. 260–271). Wroclaw, Poland: Springer Nature. https://doi.org/10.1007/978-3-662-44777-2_22
Charikar, Moses, Monika H Henzinger, and Huy L. Nguyễn. “Online Bipartite Matching with Decomposable Weights.” In 22nd Annual European Symposium on Algorithms, 8737:260–71. Springer Nature, 2014. https://doi.org/10.1007/978-3-662-44777-2_22.
M. Charikar, M. H. Henzinger, and H. L. Nguyễn, “Online bipartite matching with decomposable weights,” in 22nd Annual European Symposium on Algorithms, Wroclaw, Poland, 2014, vol. 8737, pp. 260–271.
Charikar M, Henzinger MH, Nguyễn HL. 2014. Online bipartite matching with decomposable weights. 22nd Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LNCS, vol. 8737, 260–271.
Charikar, Moses, et al. “Online Bipartite Matching with Decomposable Weights.” 22nd Annual European Symposium on Algorithms, vol. 8737, Springer Nature, 2014, pp. 260–71, doi:10.1007/978-3-662-44777-2_22.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 1409.2139