When LP is the cure for your matching woes : Improved bounds for stochastic matchings

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

Research output: Contribution to journalArticleAcademicpeer-review

43 Citations (Scopus)
2 Downloads (Pure)

Abstract

Consider a random graph model where each possible edge e is present independently with some probability p_e . 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 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 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 et al. (ICALP’09, LNCS, vol. 5555, pp. 266–278, [2009]). * We introduce a generalization of the stochastic online matching problem (Feldman et al. in FOCS’09, pp. 117–126, [2009]) that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.
Original languageEnglish
Pages (from-to)733-762
JournalAlgorithmica
Volume63
Issue number4
DOIs
Publication statusPublished - 2012

Fingerprint

Approximation algorithms
Matching Problem
Approximation Algorithms
Graph in graph theory
LP Rounding
Query
Kidney
Graph Model
Approximation
Random Graphs
Bipartite Graph
Maximise
Uncertainty
Vertex of a graph
Modeling
Model

Cite this

Bansal, N. ; Gupta, Anupam ; Liu, Jian ; Mestre, J. ; Nagarajan, V. ; Rudra, A. / When LP is the cure for your matching woes : Improved bounds for stochastic matchings. In: Algorithmica. 2012 ; Vol. 63, No. 4. pp. 733-762.
@article{15903ade9f1f4fedb6e2b5c48c4c077b,
title = "When LP is the cure for your matching woes : Improved bounds for stochastic matchings",
abstract = "Consider a random graph model where each possible edge e is present independently with some probability p_e . 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 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 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 et al. (ICALP’09, LNCS, vol. 5555, pp. 266–278, [2009]). * We introduce a generalization of the stochastic online matching problem (Feldman et al. in FOCS’09, pp. 117–126, [2009]) that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.",
author = "N. Bansal and Anupam Gupta and Jian Liu and J. Mestre and V. Nagarajan and A. Rudra",
year = "2012",
doi = "10.1007/s00453-011-9511-8",
language = "English",
volume = "63",
pages = "733--762",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "4",

}

When LP is the cure for your matching woes : Improved bounds for stochastic matchings. / Bansal, N.; Gupta, Anupam; Liu, Jian; Mestre, J.; Nagarajan, V.; Rudra, A.

In: Algorithmica, Vol. 63, No. 4, 2012, p. 733-762.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Bansal, N.

AU - Gupta, Anupam

AU - Liu, Jian

AU - Mestre, J.

AU - Nagarajan, V.

AU - Rudra, A.

PY - 2012

Y1 - 2012

N2 - Consider a random graph model where each possible edge e is present independently with some probability p_e . 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 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 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 et al. (ICALP’09, LNCS, vol. 5555, pp. 266–278, [2009]). * We introduce a generalization of the stochastic online matching problem (Feldman et al. in FOCS’09, pp. 117–126, [2009]) 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 . 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 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 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 et al. (ICALP’09, LNCS, vol. 5555, pp. 266–278, [2009]). * We introduce a generalization of the stochastic online matching problem (Feldman et al. in FOCS’09, pp. 117–126, [2009]) that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.

U2 - 10.1007/s00453-011-9511-8

DO - 10.1007/s00453-011-9511-8

M3 - Article

VL - 63

SP - 733

EP - 762

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -