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

• Suresh (or) Ryan, can you please add a tag named "hardness-of-approximation" and tag this question. I cannot add new tags with my current reputation :( Also, since long tags (> 20 chars) are not allowed, it should be hardness-of-approx I guess. Sep 14, 2010 at 3:12
• Hi Shiva, I added hardness-of-approx tag as you suggested but I personally think approximation-hardness sounds nicer and should be possible as it is shorter than approximation-algorithms. Sep 14, 2010 at 4:01
• Nicely chosen first sentence. ;) Nov 1, 2010 at 12:04

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

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.

• is the maximal matching algorithm really greedy ? Apr 10, 2012 at 23:41
• Yes, since it makes a locally optimal choice at each step. The algorithm actually makes a locally /feasible/ choice, but since the edges are unweighted this is also an optimal choice. Apr 11, 2012 at 6:15

Given a directed graph, find the acyclic subgraph with maximum number of edges.

Trivial 2-approximation algorithm: Pick an arbitrary ordering of vertices and take either the forward edges or backward edges.

Beating the 2-approximation is known to be Unique-games hard(although it might not be NP-hard).

• Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph Venkatesan Guruswami, Rajsekar Manokaran and Prasad Raghavendra.

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.

• The Nemhauser-Wolsey-Fisher analysis of the greedy algorithm is only for the case of maximizing subject to a simple cardinality constraint. Greedy gives only a $1/2$-approximation even for the simple partition matroid. The $(1-1/e)$-approximation for maximizing a submodular function subject to an arbitrary matroid is a recent result due to Vondrak and others (including myself). It relies on several tools and is not a greedy algorithm. Dec 3, 2011 at 2:55
• Ofcourse, my mistake. Edited the answer to reflect the correction. Apr 8, 2012 at 22:41

Greedy gives a (1-1/e) approximation to Max-k-cover, and this cannot be improved unless P=NP.

• I think this is the same problem as is @AshwinkumarBV's answer, which I guess was posted while I was typing mine... Sep 13, 2010 at 2:18

Finding a minimum degree MST. It is np-hard as finding a hamiltonian path is a special case. A local search algorithm gives to within an additive constant 1.

Reference

Approximating the minimum-degree Steiner tree to within one of optimal

The $k$-center problem is a clustering problem, in which we are given a complete undirected graph $G = (V,E)$ with a distance $d_{ij} \geq 0$ between each pair of vertices $i,j \in V$. The distances obey the triangle inequality and model similarity. We are also given an integer $k$.

In the problem, we have to find $k$ clusters that group together the vertices that are most similar into clusters together. We choose a set $S \subseteq V, |S| = k$ of $k$ cluster centers. Each vertex will assign itself to the closest cluster center grouping the vertices into $k$ different clusters. The objective is to minimize the maximum distance of a vertex to its cluster center. So geometrically, we want to find the centers of $k$ different balls of the same radius $r$ that cover all points so that $r$ is as small as possible.

The optimal algorithm is greedy, and also very simple and intuitive. We first pick a vertex $i \in V$ arbitrarily and put it in our set of $S$ cluster centers. We then pick the next cluster center such that it is as far away as possible from all the other cluster centers. So while $|S| < k$, we repeatedly find a vertex $j \in V$ for which the distance $d(j,S)$ is maximized and add it to $S$. Once $|S| = k$ we are done.

The described algorithm is a $2$-approximation algorithm for the $k$-center problem. In fact, if there exists a $\rho$-approximation algorithm for the problem with $\rho < 2$ then $P = NP$. This can be shown easily with a reduction from the NP-complete dominating set problem by showing we can find a dominating set of size at most $k$ iff an instance of the $k$-center problem in which all distances are either 1 or 2 has optimal value 1. The algorithm and analysis is given by Gonzales, Clustering to minimize the maximum intercluster distance, 1985. Another variant of a $2$-approximation is given by Hochbaum and Shmoys, A best possible heuristic for the k-center problem, 1985.

Graham's list scheduling procedure is optimal for precedence constrained scheduling on identical machines $P|prec|C_{max}$ unless a new variant of the unique games conjecture by Bansal and Khot is false.

Maybe this would also interest you (adapted from Methods to translate global constraints to local constraints)

Since greedy methods (more correctly local methods) employ only local information to achieve global optimisation, if ways are found which are able to transform global conditions to conditons able to be used employing only local information, this provides a (globally) optimal solution to problems using greedy/local techniques only.

References:

There are a couple of references which tackle the problem of translating global evaluation functions (or constraints) to local ones (using local information) and their consistency (i.e convergence to same global optimum):

Abstract (from 1. above)

This paper presents a new look on computational evolution from the aspect of the locality and globality of evaluation functions for solving classical combinatorial problem: the kcoloring Problem (decision problem) and the Minimum Coloring Problem (optimization problem). We first review current algorithms and model the coloring problem as a multi-agent system. We then show that the essential difference between traditional algorithms (Local Search, such as Simulated Annealing) and distributed algorithms (such as the Alife&AER model) lies in the evaluation function: Simulated Annealing uses global information to evaluate the whole system state, which is called the Global Evaluation Function (GEF) method; the Alife&AER model uses local information to evaluate the state of a single agent, which is called the Local Evaluation Function (LEF) method. We compare the performances of LEF and GEF methods for solving the k-coloring Problems and the Minimum Coloring Problems. The computer experimental results show that the LEF is comparable to GEF methods (Simulated Annealing and Greedy), in many problem instances the LEF beats GEF methods. At the same time, we analyze the relationship between GEF and LEF: consistency and inconsistency. The Consistency Theorem shows that Nash Equilibria of an LEF is identical to local optima of a GEF when the LEF is consistent with the GEF. This theorem partly explains why the LEF can lead the system to a global goal. Some rules for constructing a consistent LEF are proposed. In addition to consistency, we give a picture of the LEF and GEF and show their differences in exploration heuristics.

Specificaly the paper addresses methods to determnine whether a local function (LEF) is consistent with a global function (GEF) and methods to construct consistent LEFs from given GEFs (Consistency theorem).

Excerpt from Conclusion section (from 1. above)

This paper is just the beginning of LEF&GEF studies. In addition to the research report above, there is still a lot of future work: more experiments on LEF methods; analytical study on LEF; sufficiency of local information for LEF; and the existence of a consistent GEF for any LEF; Is the consistency concept sufficient? Since Genetic Algorithms also have an evaluation function (fitness function), can we apply LEF&GEF to Genetic Algorithms? … It is our intention to study and attempt to answer all of these questions