When LP is the cure for your matching woes: improved bounds for stochastic matchings
From MaRDI portal
Publication:692633
DOI10.1007/S00453-011-9511-8zbMATH Open1254.05145arXiv1008.5356OpenAlexW1909971775MaRDI QIDQ692633FDOQ692633
Julián Mestre, Atri Rudra, Jian Li, Viswanath Nagarajan, N. Bansal, Anupam Gupta
Publication date: 6 December 2012
Published in: Algorithmica (Search for Journal in Brave)
Abstract: Consider a random graph model where each possible edge is present independently with some probability . Given these probabilities, we want to build a large/heavy matching in the randomly generated graph. However, the only way we can find out whether an edge is present or not is to query it, and if the edge is indeed present in the graph, we are forced to add it to our matching. Further, each vertex is allowed to be queried at most times. How should we adaptively query the edges to maximize the expected weight of the matching? We consider several matching problems in this general framework (some of which arise in kidney exchanges and online dating, and others arise in modeling online advertisements); we give LP-rounding based constant-factor approximation algorithms for these problems. Our main results are the following: We give a 4 approximation for weighted stochastic matching on general graphs, and a 3 approximation on bipartite graphs. This answers an open question from [Chen etal ICALP 09]. Combining our LP-rounding algorithm with the natural greedy algorithm, we give an improved 3.46 approximation for unweighted stochastic matching on general graphs. We introduce a generalization of the stochastic online matching problem [Feldman etal FOCS 09] that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.
Full work available at URL: https://arxiv.org/abs/1008.5356
Recommendations
- When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)
- 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
Linear programming (90C05) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- AdWords and generalized online matching
- On the complexity of approximating \(k\)-set packing
- Adaptivity and approximation for stochastic packing problems
- Online stochastic matching: online actions based on offline statistics
- Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
- Dependent rounding and its applications to approximation algorithms
- Title not available (Why is that?)
- Boosted sampling
- Improved Bounds for Online Stochastic Matching
- Approximating Matches Made in Heaven
- Online Stochastic Matching: Beating 1-1/e
- Multi-armed Bandits with Metric Switching Costs
- Approximation Algorithms for 2-Stage Stochastic Optimization Problems
- Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- Finding Large Independent Sets in Graphs and Hypergraphs
- Online Weighted Matching
- Randomized metarounding
- Budget constrained auctions with heterogeneous items
- Commitment under uncertainty: Two-stage stochastic matching problems
- On k-Column Sparse Packing Programs
- On the fractional matching polytope of a hypergraph
- When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
Cited In (24)
- Approximating Matches Made in Heaven
- Stochastic graph exploration with limited resources
- Online Contention Resolution Schemes with Applications to Bayesian Selection Problems
- Title not available (Why is that?)
- Exact Bounds for the Stochastic Upward Matching Problem
- Title not available (Why is that?)
- Approximation algorithms for stochastic combinatorial optimization problems
- Improved bounds in stochastic matching and optimization
- Adaptive Submodular Ranking and Routing
- An adversarial model for scheduling with testing
- Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
- Stochastic graph exploration
- Stochastic Probing with Increasing Precision
- Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries
- Submodular Stochastic Probing on Matroids
- On the adaptivity gap of stochastic orienteering
- Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms
- Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
- Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
- Stochastic Unsplittable Flows
- A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems
- Stochastic packing integer programs with few queries
- Non-adaptive stochastic score classification and explainable halfspace evaluation
- Improved Approximation Algorithms for Stochastic Matching
This page was built for publication: When LP is the cure for your matching woes: improved bounds for stochastic matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692633)
