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

N. Bansal; A. Gupta; J. Liu; J. Mestre; V. Nagarajan; A. Rudra

doi:10.1007/978-3-642-15781-3_19

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

N. Bansal, A. Gupta, J. Liu, J. Mestre, V. Nagarajan, A. Rudra

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

25 Citations (Scopus)

3 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II)
Editors	M. Berg, de, U. Meyer
Place of Publication	Berlin
Publisher	Springer
Pages	218-229
ISBN (Print)	978-3-642-15780-6
DOIs	https://doi.org/10.1007/978-3-642-15781-3_19
Publication status	Published - 2010

Publication series

Name	Lecture Notes in Computer Science
Volume	6346
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-642-15781-3_19

Cite this

Bansal, N., Gupta, A., Liu, J., Mestre, J., Nagarajan, V., & Rudra, A. (2010). When LP is the cure for your matching woes: Improved bounds for stochastic matchings (Extended abstract). In M. Berg, de, & U. Meyer (Eds.), Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II) (pp. 218-229). (Lecture Notes in Computer Science; Vol. 6346). Springer. https://doi.org/10.1007/978-3-642-15781-3_19

@inproceedings{30f7fd17ba7047d38ea289e55d29fc81,

title = "When LP is the cure for your matching woes: Improved bounds for stochastic matchings (Extended abstract)",

abstract = "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.",

author = "N. Bansal and A. Gupta and J. Liu and J. Mestre and V. Nagarajan and A. Rudra",

year = "2010",

doi = "10.1007/978-3-642-15781-3_19",

language = "English",

isbn = "978-3-642-15780-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "218--229",

editor = "{Berg, de}, M. and U. Meyer",

booktitle = "Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II)",

address = "Germany",

}

Bansal, N, Gupta, A, Liu, J, Mestre, J, Nagarajan, V & Rudra, A 2010, When LP is the cure for your matching woes: Improved bounds for stochastic matchings (Extended abstract). in M Berg, de & U Meyer (eds), Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II). Lecture Notes in Computer Science, vol. 6346, Springer, Berlin, pp. 218-229. https://doi.org/10.1007/978-3-642-15781-3_19

When LP is the cure for your matching woes: Improved bounds for stochastic matchings (Extended abstract). / Bansal, N.; Gupta, A.; Liu, J. et al.
Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II). ed. / M. Berg, de; U. Meyer. Berlin: Springer, 2010. p. 218-229 (Lecture Notes in Computer Science; Vol. 6346).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - When LP is the cure for your matching woes: Improved bounds for stochastic matchings (Extended abstract)

AU - Bansal, N.

AU - Gupta, A.

AU - Liu, J.

AU - Mestre, J.

AU - Nagarajan, V.

AU - Rudra, A.

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.

U2 - 10.1007/978-3-642-15781-3_19

DO - 10.1007/978-3-642-15781-3_19

M3 - Conference contribution

SN - 978-3-642-15780-6

T3 - Lecture Notes in Computer Science

SP - 218

EP - 229

BT - Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II)

A2 - Berg, de, M.

A2 - Meyer, U.

PB - Springer

CY - Berlin

ER -

Bansal N, Gupta A, Liu J, Mestre J, Nagarajan V, Rudra A. When LP is the cure for your matching woes: Improved bounds for stochastic matchings (Extended abstract). In Berg, de M, Meyer U, editors, Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II). Berlin: Springer. 2010. p. 218-229. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-15781-3_19

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

Abstract

Publication series

Access to Document

Fingerprint

Cite this