The power of multiple choices in online stochastic matching

DOI10.1145/3519935.3520046MaRDI QIDQ6083465zbMATH OpenOpenAlexFDO

Authors Zhiyi Huang

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.02883

zbMATH Keywords

bipartite matchingonline algorithmsrandomized algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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-frac1e$ 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.

Recommendations

• Online stochastic matching: new algorithms and bounds
• Online stochastic matching: new algorithms with better bounds
• Online stochastic matching with unequal probabilities
• Improved Bounds for Online Stochastic Matching
• The Power of Rejection in Online Bottleneck Matching
• New algorithms, better bounds, and a novel model for online stochastic matching
• Online stochastic weighted matching: improved approximation algorithms
• On the power of advice and randomization for online bipartite matching

Cited in

(14)

• The Power of Rejection in Online Bottleneck Matching
• Online matching with concave returns
• Edge-weighted online bipartite matching
• Adwords in a panorama
• Online matching with stochastic rewards: advanced analyses using configuration linear programs
• Improved competitive ratio for edge-weighted online stochastic matching
• Matching algorithms in the sparse stochastic block model
• Online bipartite matching in the probe-commit model
• Prophet upper bounds for online matching and auctions
• Online deterministic minimum cost bipartite matching with delays on a line
• Online deterministic minimum cost bipartite matching with delays on a line
• Online combinatorial assignment in independence systems
• Online matching meets sampling without replacement
• A new impossibility result for online bipartite matching problems

This page was built for publication: The power of multiple choices in online stochastic matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083465)