Can I read Improved Approximation Algorithms for Stochastic-Matching Problems on EtoBox?

Improved Approximation Algorithms for Stochastic-Matching Problems by Adamczyk, Marek; Brubach, Brian; Grandoni, Fabrizio; Sankararaman, Karthik A.; Srinivasan, Aravind; Xu, Pan is a scholarly article available to read on EtoBox.

What is Improved Approximation Algorithms for Stochastic-Matching Problems about?

We consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. In this problem, we are given an undirected graph. Each edge is assigned a known, independent probability of existence and a positive weight (or profit). We must probe an edge to discover whether or not it exists. Each node is assigned a positive integer called a timeout (or a patience). On this random graph we are executing a process, which probes the edges one-by-one and gradually constructs a matching. The process is constrained in two ways. First, if a probed edge exists, it must be added irrevocably to the matching (the query-commit model). Second, the timeout of a node $v$ upper-bounds the number of edges incident to $v$ that can be probed. The goal is to maximize the expected weight of the constructed matching. For this problem, Bansal et al. (Algorithmica 2012) provided a $0.33$-approximation algorithm for bipartite graphs and a $0.25$-approximation for general graphs. We improve the approximation factors to $0.39$ and $0.269$, respectively. The main technical ingredient in our result is a novel way of probing edges according to a not-uniformly-random permut

Author

Adamczyk, Marek; Brubach, Brian; Grandoni, Fabrizio; Sankararaman, Karthik A.; Srinivasan, Aravind; Xu, Pan

Published

2020

Language

EN