  Online matching has received significant attention over the last 15 years due
to its close connection to Internet advertising. As the seminal work of Karp,
Vazirani, and Vazirani has an optimal (1 - 1/e) competitive ratio in the
standard adversarial online model, much effort has gone into developing useful
online models that incorporate some stochasticity in the arrival process. One
such popular model is the "known I.I.D. model" where different customer-types
arrive online from a known distribution. We develop algorithms with improved
competitive ratios for some basic variants of this model with integral arrival
rates, including (a) the case of general weighted edges, where we improve the
best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam to 0.705;
and (b) the vertex-weighted case, where we improve the 0.7250 ratio of Jaillet
and Lu to 0.7299. We also consider an extension of stochastic rewards, a
variant where each edge has an independent probability of being present. For
the setting of stochastic rewards with non-integral arrival rates, we present a
simple optimal non-adaptive algorithm with a ratio of 1 - 1/e. For the special
case where each edge is unweighted and has a uniform constant probability of
being present, we improve upon 1 - 1/e by proposing a strengthened LP
benchmark.
