Improved Approximation Algorithms for Stochastic Matching
From MaRDI portal
Publication:3452763
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
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
