Database Reference
In-Depth Information
(2) |
L
| ≤ |
R
|, because in
M
o
, all the nodes in
L
were matched.
(3) |
R
| ≤ |
M
g
|, because every node in
R
is matched in
M
g
.
Now, (2) and (3) give us |
L
| ≤ |
M
g
|. That, together with (1), gives us |
M
o
| ≤ 2|
M
g
|, or
The latter inequality says that the competitive ratio is at least 1/2. Since we already
observed that the competitive ratio is no more than 1/2, we now conclude the ratio is ex-
actly 1/2.
8.3.4
Exercises for Section 8.3
EXERCISE
8.3.1 Define the graph
G
n
to have the 2
n
nodes
a
0
, a
1
, . . . , a
n−
1
, b
0
, b
1
, . . . , b
n−
1
and the following edges. Each node
a
i
, for
i
= 0
,
1
, . . . , n
− 1, is connected to the nodes
b
j
and
b
k
, where
j
= 2
i
mod
n
and
k
= (2
i
+ 1) mod
n
For instance, the graph
G
4
has the following edges: (
a
0
, b
0
), (
a
0
, b
1
), (
a
1
, b
2
), (
a
1
, b
3
), (
a
2
,
b
0
), (
a
2
, b
1
), (
a
3
, b
2
), and (
a
3
, b
3
).
(a) Find a perfect matching for
G
4
.
(b) Find a perfect matching for
G
5
.
!!
(c) Prove that for every
n
,
G
n
has a perfect matching.
have?
!
EXERCISE
8.3.3 Whether or not the greedy algorithm gives us a perfect matching for the
graph of
Fig. 8.1
depends on the order in which we consider the edges. Of the 6! possible
orders of the six edges, how many give us a perfect matching? Give a simple test for dis-
tinguishing those orders that do give the perfect matching from those that do not.
8.4 The Adwords Problem
We now consider the fundamental problem of search advertising, which we term the “ad-
words problem,” because it was first encountered in the Google Adwords system. We then
