Improved analysis of the greedy algorithm for stochastic matching

DOI10.1016/j.ipl.2011.05.007zbMath1260.68493OpenAlexW2010428983MaRDI QIDQ1944124

Marek Adamczyk

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.05.007

zbMATH Keywords

stochastic optimizationanalysis of algorithmsapproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Stochastic programming (90C15) Approximation algorithms (68W25)

Related Items (9)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Improved Approximation Algorithms for Stochastic Matching ⋮ Submodular Stochastic Probing on Matroids ⋮ Stochastic packing integer programs with few queries ⋮ Unnamed Item ⋮ Stochastic graph exploration with limited resources ⋮ Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries ⋮ Stochastic graph exploration ⋮ Unnamed Item

Cites Work

• When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
• Approximating Matches Made in Heaven

This page was built for publication: Improved analysis of the greedy algorithm for stochastic matching