Improved Approximation Algorithms for Stochastic Matching

DOI10.1007/978-3-662-48350-3_1zbMath1401.68359arXiv1505.01439OpenAlexW1577719727MaRDI QIDQ3452763

Joydeep Mukherjee, Marek Adamczyk, Fabrizio Grandoni

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)

Related Items (7)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Improved Approximation Algorithms for Stochastic Matching ⋮ Better bounds on the adaptivity gap of influence maximization under full-adoption feedback ⋮ Unnamed Item ⋮ Improved bounds in stochastic matching and optimization ⋮ Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts ⋮ Unnamed Item

Cites Work

• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Improved analysis of the greedy algorithm for stochastic matching
• Submodular Stochastic Probing on Matroids
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Improved Approximation Algorithms for Stochastic Matching
• Dependent rounding and its applications to approximation algorithms
• Approximating Matches Made in Heaven

This page was built for publication: Improved Approximation Algorithms for Stochastic Matching