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.
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).