Stochastic Matching with Few Queries: New Algorithms and Tools

DOI10.1137/1.9781611975482.177MaRDI QIDQ5236368zbMATH OpenOpenAlexFDO

Authors Soheil Behnezhad, Alireza Farhadi, Nima Reyhani, Mohammad T. Hajiaghayi

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Analysis of algorithms (68W40) Matching models (91B68)

Abstract: We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph $G(V,E)$ along with a parameter $pin(0,1)$ is given in the input. Each edge of $G$ is realized independently with probability $p$. The goal is to select a degree bounded (dependent only on $p$) subgraph $H$ of $G$ such that the expected size/weight of maximum realized matching of $H$ is close to that of $G$. This model of stochastic matching has attracted significant attention over the recent years due to its various applications. The most fundamental open question is the best approximation factor achievable for such algorithms that, in the literature, are referred to as non-adaptive algorithms. Prior work has identified breaking (near) half-approximation as a barrier for both weighted and unweighted graphs. Our main results are as follows: -- We analyze a simple and clean algorithm and show that for unweighted graphs, it finds an (almost) $4sqrt2-5$ ($approx0.6568$) approximation by querying $O(fraclog(1/p)p)$ edges per vertex. This improves over the state-of-the-art $0.5001$ approximate algorithm of Assadi et al. [EC'17]. -- We show that the same algorithm achieves a $0.501$ approximation for weighted graphs by querying $O(fraclog(1/p)p)$ edges per vertex. This is the first algorithm to break $0.5$ approximation barrier for weighted graphs. It also improves the per-vertex queries of the state-of-the-art by Yamaguchi and Maehara [SODA'18] and Behnezhad and Reyhani [EC'18]. Our algorithms are fundamentally different from prior works, yet are very simple and natural. For the analysis, we introduce a number of procedures that construct heavy fractional matchings. We consider the new algorithms and our analytical tools to be the main contributions of this paper.

Recommendations

• Stochastic matching with few queries: (1-ε) approximation
• Improved approximation algorithms for stochastic matching
• Online stochastic matching: new algorithms with better bounds
• Online stochastic matching: new algorithms and bounds
• Ignorance is almost bliss: near-optimal stochastic matching with few queries
• New algorithms, better bounds, and a novel model for online stochastic matching
• Online stochastic weighted matching: improved approximation algorithms
• Many-to-one matchings with lower quotas: algorithms and complexity
• Faster and simpler approximation of stable matchings
• Faster and simpler approximation of stable matchings

Cited in

(15)

• Improved analysis of the greedy algorithm for stochastic matching
• An adversarial model for scheduling with testing
• Stochastic matching on uniformly sparse graphs
• Improved approximation algorithms for stochastic matching
• When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)
• Approximating Matches Made in Heaven
• Recourse in Kidney Exchange Programs
• Ignorance is almost bliss: near-optimal stochastic matching with few queries
• Understanding the correlation gap for matchings
• Beating greedy for stochastic bipartite matching
• Stochastic minimum vertex cover in general graphs: a 3/2-approximation
• Weighted matching in the random-order streaming and robust communication models
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Query efficient weighted stochastic matching
• Special issue: Selected papers based on the presentations at the workshop ``Match-UP: Matching under preferences -- algorithms and complexity, Reykjavík, Iceand, July 2008

This page was built for publication: Stochastic Matching with Few Queries: New Algorithms and Tools

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