EUVIMEDEUVIMED entdecken
Crossref

Online Vertex-Weighted Bipartite Matching

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang

ACM Transactions on Algorithms · 31.07.2019 · 15 (3) · 1-15

DOI: 10.1145/3326169 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 17.06.2019. Verfasst von Zhiyi Huang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 46-mal zitiert (Crossref) und nennt 26 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and we prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that random arrivals help beating the 1-1/e barrier even in the vertex-weighted case. We build on the randomized primal-dual framework by Devanur et al. (SODA 2013) and design a two dimensional gain sharing function, which depends not only on the rank of the offline vertex, but also on the arrival time of the online vertex. To our knowledge, this is the first competitive ratio strictly larger than 1-1/e for an online bipartite matching problem achieved under the randomized primal-dual framework. Our algorithm has a natural interpretation that offline vertices offer a larger portion of their weights to the online vertices as time increases, and each online vertex matches the neighbor with the highest offer at its arrival.

Zitieren

APA

Huang, Z., Tang, Z. G., Wu, X., & Zhang, Y. (2019). Online Vertex-Weighted Bipartite Matching. ACM Transactions on Algorithms, 15(3), 1-15. https://doi.org/10.1145/3326169

Vancouver

Huang Z, Tang ZG, Wu X, Zhang Y. Online Vertex-Weighted Bipartite Matching. ACM Transactions on Algorithms. 2019;15(3):1-15. doi:10.1145/3326169

BibTeX
@article{Huang2019,
  author = {Huang, Zhiyi and Tang, Zhihao Gavin and Wu, Xiaowei and Zhang, Yuhao},
  title = {Online Vertex-Weighted Bipartite Matching},
  journal = {ACM Transactions on Algorithms},
  year = {2019},
  volume = {15},
  number = {3},
  pages = {1--15},
  doi = {10.1145/3326169}
}
Kostenlos starten →