39
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Shiva Kintali
    Sep 14, 2010 at 3:12
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Sep 14, 2010 at 4:01
  • 6
    $\begingroup$ Nicely chosen first sentence. ;) $\endgroup$
    – AlcubierreDrive
    Nov 1, 2010 at 12:04

9 Answers 9

Reset to default
19
$\begingroup$

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

Improve this answer
$\endgroup$
16
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ is the maximal matching algorithm really greedy ? $\endgroup$
    – Suresh Venkat
    Apr 10, 2012 at 23:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – gphilip
    Apr 11, 2012 at 6:15
11
$\begingroup$

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.
Improve this answer
$\endgroup$
11
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Dec 3, 2011 at 2:55
  • $\begingroup$ Ofcourse, my mistake. Edited the answer to reflect the correction. $\endgroup$
    – Ashwinkumar B V
    Apr 8, 2012 at 22:41
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think this is the same problem as is @AshwinkumarBV's answer, which I guess was posted while I was typing mine... $\endgroup$
    – Lev Reyzin ♦
    Sep 13, 2010 at 2:18
7
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Conditional Hardness of Precedence Constrained Scheduling on Identical Machines by Ola Svensson

Improve this answer
$\endgroup$
1
$\begingroup$

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:

  1. Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifolds (Journal of Machine Learning Research 4 (2003))
  2. Global optimization using local information with applications to flow control, Bartal, Y.
  3. Why Natural Gradient?, Amari S., Douglas S.C.
  4. Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation, Awerbuch, Baruch, Azar, Y.
  5. Learning with Local and Global Consistency
  6. Constraint Satisfaction Problems Solvable by Local Consistency Methods

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

  1. Local Evaluation Functions and Global Evaluation Functions for Computational Evolution, HAN Jing, 2003
  2. Emergence from Local Evaluation Function, Han Jing and Cai Qingsheng, 2002

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.