  We consider the following stochastic optimization problem first introduced by
Chen et al. in \cite{chen}. We are given a vertex set of a random graph where
each possible edge is present with probability p_e. We do not know which edges
are actually present unless we scan/probe an edge. However whenever we probe an
edge and find it to be present, we are constrained to picking the edge and both
its end points are deleted from the graph. We wish to find the maximum matching
in this model. We compare our results against the optimal omniscient algorithm
that knows the edges of the graph and present a 0.573 factor algorithm using a
novel sampling technique. We also prove that no algorithm can attain a factor
better than 0.898 in this model.
