preprint · Research Square · 2023

Randomized ε-RANKING Algorithm for Online Trichromatic Matching

Cited by 1Open access

Abstract

Abstract We study a randomized 1/e-competitive ε-RANKING algorithm for the onlinetrichromatic matching problem. This problem involves finding matching in tripartite graphs having three disjoint sets of vertices. Our model encompasses a tripartite graph configuration, where an offline vertex set is an intermediary connecting two opposing sets. The vertices from the latter sets unfold online, arriving individually over time. ε-RANKING employs a randomization strategy where offline vertices are assigned random ranks between [0, 1]. It extends the idea of finding the lowest-ranked neighbor of the newly arrived online vertex presented by Karp et al. [1] in their RANKING algorithm. This approach exploits the principles of RANKING and matching from the domain of online bipartite matching to the more complex context of online trichromatic matching.

Cite this paper

APA 7

Pandya, K., & Maiti, A. (2023). Randomized ε-RANKING Algorithm for Online Trichromatic Matching. Research Square. https://doi.org/10.21203/rs.3.rs-3286226/v1

MLA 9

Pandya, Komal, and Abyayananda Maiti. “Randomized ε-RANKING Algorithm for Online Trichromatic Matching.” Research Square, 2023, https://doi.org/10.21203/rs.3.rs-3286226/v1.

Chicago

Pandya, Komal, and Abyayananda Maiti. 2023. “Randomized ε-RANKING Algorithm for Online Trichromatic Matching.” Research Square. https://doi.org/10.21203/rs.3.rs-3286226/v1.

Harvard

Pandya, K. and Maiti, A. (2023) ‘Randomized ε-RANKING Algorithm for Online Trichromatic Matching’, Research Square. Available at: https://doi.org/10.21203/rs.3.rs-3286226/v1.

BibTeX

@misc{pandya2023randomized,
  title = {{Randomized ε-RANKING Algorithm for Online Trichromatic Matching}},
  author = {Pandya, Komal and Maiti, Abyayananda},
  journal = {Research Square},
  year = {2023},
  doi = {10.21203/rs.3.rs-3286226/v1}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.