Randomized ϵ-RANKING Algorithm for Online Trichromatic Matching

Abstract

We present a novel ${1}/{e}$ -competitive randomized $\epsilon $ -RANKING algorithm for the unweighted online trichromatic 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 opposite sets. The vertices from the latter sets arrive online individually over time. $\epsilon $ -RANKING employs a randomization strategy where offline vertices are assigned random ranks between [0, 1]. This approach exploits the principles of the $\bigg (1-\cfrac {1}{e}\bigg)$ -competitive randomized RANKING algorithm from the domain of online bipartite matching to the more complex context of online trichromatic matching. Furthermore, with numerical experiments, we demonstrate the effectiveness of our algorithm, both with real-world and synthetic data. This work addresses the challenges of online trichromatic matching and sets a benchmark for competitive algorithms within this domain.

Keywords

• Randomized online matching
• tripartite graph matching
• online trichromatic matching
• ϵ-RANKING algorithm
• competitive analysis