Randomized ϵ-RANKING Algorithm for Online Trichromatic Matching
We present a novel <inline-formula> <tex-math notation="LaTeX">${1}/{e}$ </tex-math></inline-formula>-competitive randomized <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>-RANKING algorithm for...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10440337/ |
| _version_ | 1797293279433195520 |
|---|---|
| author | Komal Pandya Abyayananda Maiti |
| author_facet | Komal Pandya Abyayananda Maiti |
| author_sort | Komal Pandya |
| collection | DOAJ |
| description | We present a novel <inline-formula> <tex-math notation="LaTeX">${1}/{e}$ </tex-math></inline-formula>-competitive randomized <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>-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. <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>-RANKING employs a randomization strategy where offline vertices are assigned random ranks between [0, 1]. This approach exploits the principles of the <inline-formula> <tex-math notation="LaTeX">$\bigg (1-\cfrac {1}{e}\bigg)$ </tex-math></inline-formula>-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. |
| first_indexed | 2024-03-07T20:10:36Z |
| format | Article |
| id | doaj.art-24a4711eaf6e49378aa1d33bf4fb905c |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-07T20:10:36Z |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-24a4711eaf6e49378aa1d33bf4fb905c2024-02-28T00:01:20ZengIEEEIEEE Access2169-35362024-01-0112282352824610.1109/ACCESS.2024.336779410440337Randomized ϵ-RANKING Algorithm for Online Trichromatic MatchingKomal Pandya0https://orcid.org/0000-0003-2202-0451Abyayananda Maiti1Department of Computer Science and Engineering, Indian Institute of Technology Patna, Patna, Bihar, IndiaDepartment of Computer Science and Engineering, Indian Institute of Technology Patna, Patna, Bihar, IndiaWe present a novel <inline-formula> <tex-math notation="LaTeX">${1}/{e}$ </tex-math></inline-formula>-competitive randomized <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>-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. <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>-RANKING employs a randomization strategy where offline vertices are assigned random ranks between [0, 1]. This approach exploits the principles of the <inline-formula> <tex-math notation="LaTeX">$\bigg (1-\cfrac {1}{e}\bigg)$ </tex-math></inline-formula>-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.https://ieeexplore.ieee.org/document/10440337/Randomized online matchingtripartite graph matchingonline trichromatic matchingϵ-RANKING algorithmcompetitive analysis |
| spellingShingle | Komal Pandya Abyayananda Maiti Randomized ϵ-RANKING Algorithm for Online Trichromatic Matching IEEE Access Randomized online matching tripartite graph matching online trichromatic matching ϵ-RANKING algorithm competitive analysis |
| title | Randomized ϵ-RANKING Algorithm for Online Trichromatic Matching |
| title_full | Randomized ϵ-RANKING Algorithm for Online Trichromatic Matching |
| title_fullStr | Randomized ϵ-RANKING Algorithm for Online Trichromatic Matching |
| title_full_unstemmed | Randomized ϵ-RANKING Algorithm for Online Trichromatic Matching |
| title_short | Randomized ϵ-RANKING Algorithm for Online Trichromatic Matching |
| title_sort | randomized x03f5 ranking algorithm for online trichromatic matching |
| topic | Randomized online matching tripartite graph matching online trichromatic matching ϵ-RANKING algorithm competitive analysis |
| url | https://ieeexplore.ieee.org/document/10440337/ |
| work_keys_str_mv | AT komalpandya randomizedx03f5rankingalgorithmforonlinetrichromaticmatching AT abyayanandamaiti randomizedx03f5rankingalgorithmforonlinetrichromaticmatching |