Skip to content

Opening book details…

Can I read The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm on EtoBox?

The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm by Assadi, Sepehr; Khanna, Sanjeev; Li, Yang is a scholarly article available to read on EtoBox.

What is The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm about?

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 $\frac{1}{2}-\epsilon$ for any $\epsilon > 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$ of $G$ w

Author
Assadi, Sepehr; Khanna, Sanjeev; Li, Yang
Published
2017
Language
EN

More by Assadi, Sepehr; Khanna, Sanjeev; Li, Yang

Browse all works by Assadi, Sepehr; Khanna, Sanjeev; Li, Yang