Q:

Optimal greedy algorithms for NP-hard problems

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive algorithms for many problems in P. More interestingly, for some NP-hard problems the obvious and natural greedy/local algorithm results in (provably) optimal approximation factor (under suitable complexity theoretic assumptions). A classic example is the Set Cover Problem. A natural greedy algorithm gives an O(ln n) approximation factor, which is optimal unless P = NP.
Name some natural greedy/local algorithms for NP-hard problems that are provably optimal under suitable complexity theoretic assumptions.

A:

The method of conditional expectations (for derandomizing the "random assignment" algorithms for Max-Cut and Max-SAT) can be viewed as a greedy strategy: for $i=1,\ldots,n$, you pick the value of a variable $x_i$ such that the expected number of constraints satisfied in the resulting reduced instance exceeds the expected number of constraints satisfied in the current instance. (In fact, the greedy algorithm for $1/2$-approximating Max-Cut is the same as the "method of conditional expectations" algorithm for $1/2$-approximating Max-Cut.)
Since the method also works for Max-E3-SAT and achieves a $7/8$-approximation, this is an example of a greedy algorithm which is an optimal approximation unless $P=NP$ (cf. Hastad and Moshkovitz-Raz's inapproximability results for Max-E3-SAT).

A:

Vertex Cover : The best constant factor approximation algorithm involves (greedily) finding a maximal matching and picking all the vertices involved as the approximate solution. This yields a 2-approximate solution, and no better constant-factor approximation is possible unless the Unique Games Conjecture is false.
Subhash Khot and Oded Regev, Vertex cover might be hard to approximate to within 2−ε, JCSS 74(3), 2008.
Off topic : I think this is a really cute approximation algorithm, especially since it is oh-so-trivial with the benefit of hindsight.

A:

Submodular maximization with respect to cardinality constraint has a 1-1/e greedy approximation. Algorithm is due to Nemhauser, Wolsey, Fisher. NP hardness follows from np-hardness of set cover as max-coverage is a special case of submodular maximization.

