File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3519935.3520046
- Scopus: eid_2-s2.0-85132689424
- WOS: WOS:000852709400009
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: The power of multiple choices in online stochastic matching
Title | The power of multiple choices in online stochastic matching |
---|---|
Authors | |
Keywords | bipartite matching online algorithms randomized algorithms |
Issue Date | 10-Jun-2022 |
Abstract | We study the power of multiple choices in online stochastic matching. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. This paper introduces two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting, and improve the competitive ratios to 0.716, from 0.711 and 0.7 respectively. For edge-weighted matching with free disposal, we propose the Top Half Sampling algorithm. We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality. This improves the competitive ratio to 0.706, breaking the 1−1/e barrier in this setting for the first time in the literature. Finally, for the harder edge-weighted problem without free disposal, we prove that no algorithms can be 0.703 competitive, separating this setting from the aforementioned three. |
Persistent Identifier | http://hdl.handle.net/10722/333747 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Zhiyi | - |
dc.contributor.author | Shu, Xinkai | - |
dc.contributor.author | Yan, Shuyi | - |
dc.date.accessioned | 2023-10-06T08:38:45Z | - |
dc.date.available | 2023-10-06T08:38:45Z | - |
dc.date.issued | 2022-06-10 | - |
dc.identifier.uri | http://hdl.handle.net/10722/333747 | - |
dc.description.abstract | <p>We study the power of multiple choices in online stochastic matching. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. This paper introduces two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting, and improve the competitive ratios to 0.716, from 0.711 and 0.7 respectively. For edge-weighted matching with free disposal, we propose the Top Half Sampling algorithm. We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality. This improves the competitive ratio to 0.706, breaking the 1−1/<em>e</em> barrier in this setting for the first time in the literature. Finally, for the harder edge-weighted problem without free disposal, we prove that no algorithms can be 0.703 competitive, separating this setting from the aforementioned three.<br></p> | - |
dc.language | eng | - |
dc.relation.ispartof | 54th ACM Symposium on Theory of Computing (20/06/2022-24/06/2022, Rome) | - |
dc.subject | bipartite matching | - |
dc.subject | online algorithms | - |
dc.subject | randomized algorithms | - |
dc.title | The power of multiple choices in online stochastic matching | - |
dc.type | Conference_Paper | - |
dc.identifier.doi | 10.1145/3519935.3520046 | - |
dc.identifier.scopus | eid_2-s2.0-85132689424 | - |
dc.identifier.spage | 91 | - |
dc.identifier.epage | 103 | - |
dc.identifier.isi | WOS:000852709400009 | - |