Improved analysis of the greedy algorithm for stochastic matching

DOI10.1016/J.IPL.2011.05.007MaRDI QIDQ1944124zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Improved approximation algorithms for stochastic matching
• Approximating Matches Made in Heaven
• 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
• Stochastic Matching with Few Queries: New Algorithms and Tools

Cites work

• Approximating Matches Made in Heaven
• When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)

Cited in

(12)

• Approximating Matches Made in Heaven
• Stochastic graph exploration with limited resources
• Stochastic analysis of partitioning algorithms for matching problems
• Technical note -- Greedy algorithm for multiway matching with bounded regret
• Approximation algorithms for stochastic combinatorial optimization problems
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Submodular stochastic probing on matroids
• Stochastic graph exploration
• Approximation algorithms for stochastic \(k\)-TSP
• Improved approximation algorithms for stochastic matching
• Stochastic packing integer programs with few queries
• Ignorance is almost bliss: near-optimal stochastic matching with few queries

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

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