  Motivated by the fact that in several cases a matching in a graph is stable
if and only if it is produced by a greedy algorithm, we study the problem of
computing a maximum weight greedy matching on weighted graphs, termed
GreedyMatching. In wide contrast to the maximum weight matching problem, for
which many efficient algorithms are known, we prove that GreedyMatching is
strongly NP-hard and APX-complete, and thus it does not admit a PTAS unless
P=NP, even on graphs with maximum degree at most 3 and with at most three
different integer edge weights. Furthermore we prove that GreedyMatching is
strongly NP-hard if the input graph is in addition bipartite. Moreover we
consider two natural parameters of the problem, for which we establish a sharp
threshold behavior between NP-hardness and tractability. On the positive side,
we present a randomized approximation algorithm (RGMA) for GreedyMatching on a
special class of weighted graphs, called bush graphs. We highlight an
unexpected connection between RGMA and the approximation of maximum cardinality
matching in unweighted graphs via randomized greedy algorithms. We show that,
if the approximation ratio of RGMA is $\rho$, then for every $\epsilon>0$ the
randomized MRG algorithm of [Aronson et al., Rand. Struct. Alg. 1995] gives a
$(\rho-\epsilon)$-approximation for the maximum cardinality matching. We
conjecture that a tight bound for $\rho$ is $\frac{2}{3}$; we prove our
conjecture true for two subclasses of bush graphs. Proving a tight bound for
the approximation ratio of MRG on unweighted graphs (and thus also proving a
tight value for $\rho$) is a long-standing open problem [Poloczek and Szegedy;
FOCS 2012]. This unexpected relation of our RGMA algorithm with the MRG
algorithm may provide new insights for solving this problem.
