When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings

DOI10.1007/978-3-642-15781-3_19zbMath1287.05111OpenAlexW2896902984MaRDI QIDQ3586398

Viswanath Nagarajan, Atri Rudra, Nikhil Bansal, Anupam Gupta, Julián Mestre, Jian Li

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

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

Related Items (7)

Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm ⋮ A mixed-integer programming approach for locating jamming devices in a flow-jamming attack ⋮ Improved analysis of the greedy algorithm for stochastic matching ⋮ Accelerating benders decomposition with heuristicmaster problem solutions ⋮ 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

This page was built for publication: When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings