  Motivated by an application in kidney exchange, we study the following
query-commit problem: we are given the set of vertices of a non-bipartite graph
G. The set of edges in this graph are not known ahead of time. We can query any
pair of vertices to determine if they are adjacent. If the queried edge exists,
we are committed to match the two endpoints. Our objective is to maximize the
size of the matching.
  This restriction in the amount of information available to the algorithm
constraints us to implement myopic, greedy-like algorithms. A simple
deterministic greedy algorithm achieves a factor 1/2 which is tight for
deterministic algorithms. An important open question in this direction is to
give a randomized greedy algorithm that has a significantly better
approximation factor. This question was first asked almost 20 years ago by Dyer
and Frieze [9] where they showed that a natural randomized strategy of picking
edges uniformly at random doesn't help and has an approximation factor of 1/2 +
o(1). They left it as an open question to devise a better randomized greedy
algorithm. In subsequent work, Aronson, Dyer, Frieze, and Suen [2] gave a
different randomized greedy algorithm and showed that it attains a factor 0.5 +
epsilon where epsilon is 0.0000025.
  In this paper we propose and analyze a new randomized greedy algorithm for
finding a large matching in a general graph and use it to solve the query
commit problem mentioned above. We show that our algorithm attains a factor of
at least 0.56, a significant improvement over 0.50000025. We also show that no
randomized algorithm can have an approximation factor better than 0.7916 for
the query commit problem. For another large and interesting class of randomized
algorithms that we call vertex-iterative algorithms, we show that no
vertex-iterative algorithm can have an approximation factor better than 0.75.
