TY - GEN
T1 - When LP is the cure for your matching woes
T2 - 18th Annual European Symposium on Algorithms, ESA 2010
AU - Bansal, Nikhil
AU - Gupta, Anupam
AU - Li, Jian
AU - Mestre, Julián
AU - Nagarajan, Viswanath
AU - Rudra, Atri
PY - 2010
Y1 - 2010
N2 - Consider a random graph model where each possible edge e is present independently with some probability p e . We are given these numbers p e , and 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 i is allowed to be queried at most t i 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: • We give a 5.75-approximation for weighted stochastic matching on general graphs, and a 5-approximation on bipartite graphs. This answers an open question from [Chen et al. ICALP 09]. • Combining our LP-rounding algorithm with the natural greedy algorithm, we give an improved 3.88-approximation for unweighted stochastic matching on general graphs and 3.51-approximation on bipartite graphs. • We introduce a generalization of the stochastic online matching problem [Feldman et al. FOCS 09] that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.
AB - Consider a random graph model where each possible edge e is present independently with some probability p e . We are given these numbers p e , and 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 i is allowed to be queried at most t i 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: • We give a 5.75-approximation for weighted stochastic matching on general graphs, and a 5-approximation on bipartite graphs. This answers an open question from [Chen et al. ICALP 09]. • Combining our LP-rounding algorithm with the natural greedy algorithm, we give an improved 3.88-approximation for unweighted stochastic matching on general graphs and 3.51-approximation on bipartite graphs. • We introduce a generalization of the stochastic online matching problem [Feldman et al. FOCS 09] that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.
UR - http://www.scopus.com/inward/record.url?scp=78349256713&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78349256713&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-15781-3_19
DO - 10.1007/978-3-642-15781-3_19
M3 - Conference contribution
AN - SCOPUS:78349256713
SN - 3642157807
SN - 9783642157806
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 218
EP - 229
BT - Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
Y2 - 6 September 2010 through 8 September 2010
ER -