Recall that for a problem in which the goal is to maximize some underlying

quantity, gradient descent has a natural upside-down analogue,

in which one repeatedly moves from the current solution to a solution

of strictly greater value. Naturally, we could call this a gradient ascent

algorithm . (Often in the literature youll also see such methods referred

to as hill-climbing algorithms.)

By straight symmetry, the observations weve made in this chapter

about gradient descent carry over to gradient ascent: For many problems

you can easily end up with a local optimum that is not very good. But

sometimes one encounters problemsas we saw, for example, with

the Maximum-Cut and Labeling Problemsfor which a local search

algorithm comes with a very strong guarantee: Every local optimum is

close in value to the global optimum. We now consider the Bipartite

Matching Problem and find that the same phenomenon happens here as

well.

Thus, consider the following Gradient Ascent Algorithm for finding

a matching in a bipartite graph.

As long as there is an edge whose endpoints are unmatched, add it to

the current matching. When there is no longer such an edge, terminate

with a locally optimal matching.

(a) Give an example of a bipartite graph G for which this gradient ascent

algorithm does not return the maximum matching.

(b) Let M and M_ be matchings in a bipartite graph G . Suppose that

|M_| > 2|M| . Show that there is an edge e_ M_ such that M {e_} is

a matching in G .

(c) Use (b) to conclude that any locally optimal matching returned by

the gradient ascent algorithm in a bipartite graph G is at least half

as large as a maximum matching in G .