The stochastic matching problem: Beating half with a non-Adaptive algorithm

Sepehr Assadi, Sanjeev Khanna, Yang Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

In the stochastic matching problem, we are given a general (not necessarily bipartite) graph G(V, E), where each edge in E is realized with some constant probability p > 0 and the goal is to compute a bounded-degree (bounded by a function depending only on p) subgraph H of G such that the expected maximum matching size in H is close to the expected maximum matching size in G. The algorithms in this setting are considered non-Adaptive as they have to choose the subgraph H without knowing any information about the set of realized edges in G. Originally motivated by an application to kidney exchange, the stochastic matching problem and its variants have received significant attention in recent years. The state-of-The-Art non-Adaptive algorithms for stochastic matching achieve an approximation ratio of 12 -ϵ for any ϵ > 0, naturally raising the question that if 1/2 is the limit of what can be achieved with a non-Adaptive algorithm. In this work, we resolve this question by presenting the first algorithm for stochastic matching with an approximation guarantee that is strictly better than 1/2: The algorithm computes a subgraph H ofG with the maximum degree O (log (1/p)/ p) such that the ratio of expected size of a maximum matching in realizations of H and G is at least 1/2+δ0 for some absolute constant δ0 > 0. The degree bound on H achieved by our algorithm is essentially the best possible (up to an O(log (1/p)) factor) for any constant factor approximation algorithm, since an Ω( 1 p ) degree in H is necessary for a vertex to acquire at least one incident edge in a realization. Our result makes progress towards answering an open problem of Blum et al. (EC 2015) regarding the possibility of achieving a (1 - ϵ )-Approximation for the stochastic matching problem using non-Adaptive algorithms. From the technical point of view, a key ingredient of our algorithm is a structural result showing that a graph whose expected maximum matching size is opt always contains a b-matching of size (essentially) b opt, for b = 1 p .

Original languageEnglish (US)
Title of host publicationEC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages99-116
Number of pages18
ISBN (Electronic)9781450345279
DOIs
StatePublished - Jun 20 2017
Externally publishedYes
Event18th ACM Conference on Economics and Computation, EC 2017 - Cambridge, United States
Duration: Jun 26 2017Jun 30 2017

Publication series

NameEC 2017 - Proceedings of the 2017 ACM Conference on Economics and Computation

Conference

Conference18th ACM Conference on Economics and Computation, EC 2017
Country/TerritoryUnited States
CityCambridge
Period6/26/176/30/17

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Statistics and Probability
  • Computational Mathematics
  • Economics and Econometrics

Keywords

  • Kidney exchange
  • Stochastic matching

Fingerprint

Dive into the research topics of 'The stochastic matching problem: Beating half with a non-Adaptive algorithm'. Together they form a unique fingerprint.

Cite this