Improved approximation algorithms for stochastic matching

DOI10.1007/978-3-662-48350-3_1MaRDI QIDQ3452763zbMATH OpenOpenAlexFDO

Authors Marek Adamczyk, Fabrizio Grandoni, Joydeep Mukherjee

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Matching models (91B68)

Abstract: In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every edge is assigned a probability of existence and a positive profit, and each node is assigned a positive integer called timeout. We know whether an edge exists or not only after probing it. On this random graph we are executing a process, which one-by-one probes the edges and gradually constructs a matching. The process is constrained in two ways: once an edge is taken it cannot be removed from the matching, and the timeout of node $v$ upper-bounds the number of edges incident to $v$ that can be probed. The goal is to maximize the expected profit of the constructed matching. For this problem Bansal et al. (Algorithmica 2012) provided a $3$-approximation algorithm for bipartite graphs, and a $4$-approximation for general graphs. In this work we improve the approximation factors to $2.845$ and $3.709$, respectively. We also consider an online version of the bipartite case, where one side of the partition arrives node by node, and each time a node $b$ arrives we have to decide which edges incident to $b$ we want to probe, and in which order. Here we present a $4.07$-approximation, improving on the $7.92$-approximation of Bansal et al. The main technical ingredient in our result is a novel way of probing edges according to a random but non-uniform permutation. Patching this method with an algorithm that works best for large probability edges (plus some additional ideas) leads to our improved approximation factors.

Recommendations

• When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Approximating Matches Made in Heaven
• Stochastic Matching with Few Queries: New Algorithms and Tools
• Stochastic matching on uniformly sparse graphs

Cites work

• Approximating Matches Made in Heaven
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Dependent rounding and its applications to approximation algorithms
• Improved analysis of the greedy algorithm for stochastic matching
• Improved approximation algorithms for stochastic matching
• Submodular stochastic probing on matroids
• When LP is the cure for your matching woes: improved bounds for stochastic matchings

Cited in

(30)

• Faster and simpler approximation of stable matchings
• Improved bounds in stochastic matching and optimization
• Improved analysis of the greedy algorithm for stochastic matching
• Improved deterministic distributed matching via rounding
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Stochastic matching on uniformly sparse graphs
• Stochastic matching with commitment
• Approximation algorithms for stochastic combinatorial optimization problems
• Improved approximation algorithms for stochastic matching
• When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)
• Improved Bounds for Online Stochastic Matching
• Approximating Matches Made in Heaven
• Exact Bounds for the Stochastic Upward Matching Problem
• Randomized $\tilde{O}(M(|V|))$ Algorithms for Problems in Matching Theory
• Stochastic analysis of partitioning algorithms for matching problems
• Ignorance is almost bliss: near-optimal stochastic matching with few queries
• Approximation algorithms for stochastic k-TSP
• Beating greedy for stochastic bipartite matching
• Stochastic Matching with Few Queries: New Algorithms and Tools
• Improved bounds in stochastic matching and optimization
• New deterministic approximation algorithms for fully dynamic matching
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• An Improved Approximation Algorithm for the Matching Augmentation Problem
• An improvement on Łuczak's connected matchings method
• Better bounds on the adaptivity gap of influence maximization under full-adoption feedback
• Online bipartite matching in the probe-commit model
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• On approximating stochastic independent sets
• Online stochastic matching with edge arrivals
• 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: Improved approximation algorithms for stochastic matching

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