Consider a random graph model where each possible edge e is present independently with
some probability pe. We are just given these numbers pe, 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
ti 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.