Approximating Matches Made in Heaven

DOI10.1007/978-3-642-02927-1_23MaRDI QIDQ3638040zbMATH OpenOpenAlexFDO

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

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

dichotomous preferencekidney exchangematching marketonline datingpatience parameterstochastic matching problem

Mathematics Subject Classification ID

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

Recommendations

• 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
• Improved approximation algorithms for stochastic matching
• Improved analysis of the greedy algorithm for stochastic matching
• Stochastic Matching with Few Queries: New Algorithms and Tools

Cited in

(33)

• Improved bounds in stochastic matching and optimization
• Improved analysis of the greedy algorithm for stochastic matching
• Stochastic packing integer programs with few queries
• An adversarial model for scheduling with testing
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Almost exact matchings
• Randomized parameterized algorithms for the kidney exchange problem
• As Close as It Gets
• Approximation algorithms for stochastic combinatorial optimization problems
• Submodular stochastic probing on matroids
• Improved approximation algorithms for stochastic matching
• When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)
• Opting into optimal matchings
• Technical note -- Assortment planning for two-sided sequential matching markets
• Stochastic graph exploration
• Ignorance is almost bliss: near-optimal stochastic matching with few queries
• Approximation algorithms for stochastic k-TSP
• Maximizing expected utility for stochastic combinatorial optimization problems
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• scientific article; zbMATH DE number 7053373 (Why is no real title available?)
• scientific article; zbMATH DE number 7650116 (Why is no real title available?)
• Better bounds on the adaptivity gap of influence maximization under full-adoption feedback
• Stochastic graph exploration with limited resources
• Stochastic Probing with Increasing Precision
• Online bipartite matching in the probe-commit model
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Maximum-expectation matching under recourse
• Toward a better understanding of randomized greedy matching
• Delegated stochastic probing
• Random order vertex arrival contention resolution schemes for matching, with applications
• Online stochastic matching with edge arrivals
• Beyond the worst case: distortion in impartial culture electorates
• On the adaptivity gap of stochastic orienteering

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

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