Database Reference
In-Depth Information
EXAMPLE
8.5 Let us consider a greedy match for the graph of
Fig. 8.1
. Suppose we order
the nodes lexicographically, that is, by order of their left node, breaking ties by the right
node. Then we consider the edges in the order (1
, a
), (1
, c
), (2
, b
), (3
, b
), (3
, d
), (4
, a
). The
first edge, (1
, a
), surely becomes part of the matching. The second edge, (1
, c
), cannot be
chosen, because node 1 already appears in the matching. The third edge, (2
, b
), is selected,
because neither node 2 nor node
b
appears in the matching so far. Edge (3
, b
) is rejected
for the match because
b
is already matched, but then (3
, d
) is added to the match because
neither 3 nor
d
has been matched so far. Finally, (4
, a
) is rejected because
a
appears in the
match. Thus, the matching produced by the greedy algorithm for this ordering of the edges
is {(1
, a
)
,
(2
, b
)
,
(3
, d
)}. As we saw, this matching is not maximal.
□
EXAMPLE
8.6 A greedy match can be even worse than that of
Example 8.5
. On the graph
of
Fig. 8.1
, any ordering that begins with the two edges (1
, a
) and (3
, b
), in either order,
will match those two pairs but then will be unable to match nodes 2 or 4. Thus, the size of
the resulting match is only 2.
□
8.3.3
Competitive Ratio for Greedy Matching
We can show a competitive ratio of 1/2 for the greedy matching algorithm of
Section 8.3.2
.
is a perfect matching of size 4. However, if the edges are presented in any of the orders
discussed in
Example 8.6
, the size of the match is only 2, or half the optimum. Since the
competitive ratio for an algorithm is the minimum over all possible inputs of the ratio of
what that algorithm achieves to the optimum result, we see that 1/2 is an upper bound on
the competitive ratio.
Suppose
M
o
is a maximal matching, and
M
g
is the matching that the greedy algorithm
produces. Let
L
be the set of left nodes that are matched in
M
o
but not in
M
g
. Let
R
be the
set of right nodes that are connected by edges to any node in
L
. We claim that every node
in
R
is matched in
M
g
. Suppose not; in particular, suppose node
r
in
R
is not matched in
M
g
. Then the greedy algorithm will eventually consider some edge (
ℓ, r
), where
ℓ
is in
L
.
At that time, neither end of this edge is matched, because we have supposed that neither
ℓ
nor
r
is ever matched by the greedy algorithm. That observation contradicts the definition
of how the greedy algorithm works; that is, the greedy algorithm would indeed match (
ℓ,
r
). We conclude that every node in
R
is matched in
M
g
.
Now, we know several things about the sizes of sets and matchings.
(1) |
M
o
| ≤ |
M
g
| + |
L
|, since among the nodes on the left, only nodes in
L
can be matched in
M
o
but not
M
g
.
