When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)

DOI10.1007/978-3-642-15781-3_19MaRDI QIDQ3586398zbMATH OpenOpenAlexFDO

Authors N. Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15781-3_19

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Linear programming (90C05) Combinatorial optimization (90C27)

Recommendations

• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Improved approximation algorithms for stochastic matching
• Stochastic Matching with Few Queries: New Algorithms and Tools
• Approximating Matches Made in Heaven
• Stochastic matching on uniformly sparse graphs

Cited in

(19)

• A mixed-integer programming approach for locating jamming devices in a flow-jamming attack
• Improved bounds in stochastic matching and optimization
• Improved analysis of the greedy algorithm for stochastic matching
• Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts
• Stochastic matching on uniformly sparse graphs
• A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
• Stochastic matching with commitment
• Two-sided online bipartite matching and vertex cover: beating the greedy algorithm
• Improved approximation algorithms for stochastic matching
• Approximating Matches Made in Heaven
• Exact Bounds for the Stochastic Upward Matching Problem
• Accelerating Benders decomposition with heuristic master problem solutions
• Dynamic stochastic matching under limited time
• Ignorance is almost bliss: near-optimal stochastic matching with few queries
• Understanding the correlation gap for matchings
• Beating greedy for stochastic bipartite matching
• Improved bounds in stochastic matching and optimization
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Special issue: Selected papers based on the presentations at the workshop ``Match-UP: Matching under preferences -- algorithms and complexity, Reykjavík, Iceand, July 2008

This page was built for publication: When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)

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