Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910892465061888 |
|---|---|
| author | Sun, Enze Tang, Zhihao Gavin Wang, Yifan |
| author_facet | Sun, Enze Tang, Zhihao Gavin Wang, Yifan |
| contents | We study the online stochastic matching problem. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal $0.5$-competitive algorithm. A recent line of work, initiated by Papadimitriou, Pollner, Saberi, and Wajc (MOR 2024), focuses on designing approximation algorithms against the online optimum. The online benchmark allows positive results surpassing the $0.5$ ratio.
In this work, adapting the order-competitive analysis by Ezra, Feldman, Gravin, and Tang (SODA 2023), we design a $0.5+Ω(1)$ order-competitive algorithm against the online benchmark with unknown arrival order. Our algorithm is significantly different from existing ones, as the known arrival order is crucial to the previous approximation algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19456 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum Sun, Enze Tang, Zhihao Gavin Wang, Yifan Data Structures and Algorithms We study the online stochastic matching problem. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal $0.5$-competitive algorithm. A recent line of work, initiated by Papadimitriou, Pollner, Saberi, and Wajc (MOR 2024), focuses on designing approximation algorithms against the online optimum. The online benchmark allows positive results surpassing the $0.5$ ratio. In this work, adapting the order-competitive analysis by Ezra, Feldman, Gravin, and Tang (SODA 2023), we design a $0.5+Ω(1)$ order-competitive algorithm against the online benchmark with unknown arrival order. Our algorithm is significantly different from existing ones, as the known arrival order is crucial to the previous approximation algorithms. |
| title | Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.19456 |