Approximating Matches Made in Heaven

DOI10.1007/978-3-642-02927-1_23zbMath1247.05237OpenAlexW1788659242MaRDI QIDQ3638040

Anna R. Karlin, Nicole Immorlica, Atri Rudra, Ning Chen, Mohammad Mahdian

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_23

zbMATH Keywords

matching marketkidney exchangeonline datingdichotomous preferencepatience parameterstochastic matching problem

Mathematics Subject Classification ID

Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Matching models (91B68)

Related Items (22)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Improved Approximation Algorithms for Stochastic Matching ⋮ Randomized parameterized algorithms for the kidney exchange problem ⋮ Technical Note—Assortment Planning for Two-Sided Sequential Matching Markets ⋮ Submodular Stochastic Probing on Matroids ⋮ Stochastic packing integer programs with few queries ⋮ On the adaptivity gap of stochastic orienteering ⋮ Better bounds on the adaptivity gap of influence maximization under full-adoption feedback ⋮ Unnamed Item ⋮ Stochastic graph exploration with limited resources ⋮ Improved analysis of the greedy algorithm for stochastic matching ⋮ Stochastic Probing with Increasing Precision ⋮ An adversarial model for scheduling with testing ⋮ Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries ⋮ Improved bounds in stochastic matching and optimization ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts ⋮ Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems ⋮ Stochastic graph exploration ⋮ Unnamed Item ⋮ Running Errands in Time: Approximation Algorithms for Stochastic Orienteering ⋮ Unnamed Item

This page was built for publication: Approximating Matches Made in Heaven