  We study the greedy-based online algorithm for edge-weighted matching with
(one-sided) vertex arrivals in bipartite graphs, and edge arrivals in general
graphs. This algorithm was first studied more than a decade ago by Korula and
P\'al for the bipartite case in the random-order model. While the weighted
bipartite matching problem is solved in the random-order model, this is not the
case in recent and exciting online models in which the online player is
provided with a sample, and the arrival order is adversarial. The greedy-based
algorithm is arguably the most natural and practical algorithm to be applied in
these models. Despite its simplicity and appeal, and despite being studied in
multiple works, the greedy-based algorithm was not fully understood in any of
the studied online models, and its actual performance remained an open question
for more than a decade.
  We provide a thorough analysis of the greedy-based algorithm in several
online models. For vertex arrivals in bipartite graphs, we characterize the
exact competitive-ratio of this algorithm in the random-order model, for any
arrival order of the vertices subsequent to the sampling phase (adversarial and
random orders in particular). We use it to derive tight analysis in the recent
adversarial-order model with a sample (AOS model) for any sample size,
providing the first result in this model beyond the simple secretary problem.
Then, we generalize and strengthen the black box method of converting results
in the random-order model to single-sample prophet inequalities, and use it to
derive the state-of-the-art single-sample prophet inequality for the problem.
Finally, we use our new techniques to analyze the greedy-based algorithm for
edge arrivals in general graphs and derive results in all the mentioned online
models. In this case as well, we improve upon the state-of-the-art
single-sample prophet inequality.
