<p>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 <em>the same</em> as the "method of conditional expectations" algorithm for $1/2$-approximating Max-Cut.)</p>

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

CC BY-SA 2.5
2010-09-13T05:05:00.947Z
2010-09-13T05:05:00.947Z
Ryan Williams
<p>Vertex Cover : The <a href="http://en.wikipedia.org/wiki/Vertex_cover#Approximate_evaluation">best constant factor approximation algorithm</a> involves (greedily) finding a maximal matching and picking all the vertices involved as the approximate solution. This yields a 2-approximate solution, and <a href="http://en.wikipedia.org/wiki/Vertex_cover#Inapproximability">no better constant-factor approximation is possible</a> unless the Unique Games Conjecture is false.</p>

<p>Subhash Khot and Oded Regev, <a href="http://dx.doi.org/10.1016%2Fj.jcss.2007.06.019">Vertex cover might be hard to approximate to within 2−ε</a>, JCSS 74(3), 2008.</p>

<p>Off topic : I think this is a really cute approximation algorithm, especially since it is oh-so-trivial with the benefit of hindsight.</p>

CC BY-SA 3.0
2012-04-10T23:41:14.577Z
is the maximal matching algorithm really greedy ?
Suresh Venkat
CC BY-SA 3.0
2012-04-11T06:15:09.723Z
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.
gphilip
CC BY-SA 2.5
2010-09-14T02:29:02.080Z
2010-09-14T02:29:02.080Z
gphilip
<blockquote>
  <p>Given a directed graph, find the acyclic subgraph with maximum number of edges.</p>
</blockquote>

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

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

<ul>
<li>Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph
Venkatesan Guruswami, Rajsekar Manokaran and Prasad Raghavendra.</li>
</ul>

CC BY-SA 2.5
2010-09-13T17:20:16.313Z
2010-09-13T17:20:16.313Z
Jagadish
<p>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.</p>

CC BY-SA 3.0
2011-12-03T02:55:24.573Z
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.
Chandra Chekuri
CC BY-SA 3.0
2012-04-08T22:41:27.407Z
Ofcourse, my mistake. Edited the answer to reflect the correction.
Ashwinkumar B V
CC BY-SA 3.0
2010-09-13T02:10:56.437Z
2012-04-08T22:39:28.233Z
2012-04-08T22:39:28.233Z
Ashwinkumar B V
<p>Greedy gives a (1-1/e) approximation to Max-k-cover, and this cannot be improved unless P=NP.</p>

CC BY-SA 2.5
2010-09-13T02:18:10.703Z
I think this is the same problem as is @AshwinkumarBV's answer, which I guess was posted while I was typing mine...
Lev Reyzin
CC BY-SA 2.5
2010-09-13T02:16:17.370Z
2010-09-13T02:16:17.370Z
Lev Reyzin
<p>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.</p>

<p>Reference</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136.1089">Approximating the minimum-degree Steiner tree to within one of optimal</a></p>

CC BY-SA 2.5
2010-09-14T01:23:10.247Z
2010-09-14T01:23:10.247Z
Ashwinkumar B V
<p>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$.</p>

<p>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.</p>

<p>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| &lt; 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. </p>

<p>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 &lt; 2$ then $P = NP$. This can be shown easily with a reduction from the NP-complete <a href="http://en.wikipedia.org/wiki/Dominating_set" rel="nofollow">dominating set problem</a> 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 <a href="https://www.cs.ucsb.edu/~teo/papers/Ktmm.pdf" rel="nofollow">Gonzales, Clustering to minimize the maximum intercluster distance, 1985</a>. Another variant of a $2$-approximation is given by <a href="http://signal.ece.utexas.edu/~vishal/kcenters.pdf" rel="nofollow">Hochbaum and Shmoys, A best possible heuristic for the k-center problem, 1985</a>.</p>

CC BY-SA 3.0
2012-04-10T23:22:06.813Z
2012-04-11T12:24:01.273Z
2012-04-11T12:24:01.273Z
Juho
<p>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.</p>

<p><a href="http://www.nada.kth.se/~osven/papers/PCmaxFull5Nov.pdf">Conditional Hardness of Precedence Constrained Scheduling on Identical Machines</a> by Ola Svensson</p>

CC BY-SA 2.5
2010-09-19T09:43:24.507Z
2010-09-19T09:43:24.507Z
Oleksandr Bondarenko
<p>Maybe this would also interest you (adapted from <a href="https://math.stackexchange.com/questions/1167456/methods-to-translate-global-constraints-to-local-constraints">Methods to translate global constraints to local constraints</a>)</p>
<p>Since greedy methods (more correctly <em>local</em> 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.</p>
<p>References:</p>
<ol>
<li><a href="https://www.jmlr.org/papers/volume4/saul03a/saul03a.pdf" rel="nofollow noreferrer">Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifolds (Journal of Machine Learning Research 4 (2003))</a></li>
<li><a href="https://ieeexplore.ieee.org/document/646119" rel="nofollow noreferrer">Global optimization using local information with applications to flow control, Bartal, Y.</a></li>
<li><a href="http://www.yaroslavvb.com/papers/amari-why.pdf" rel="nofollow noreferrer">Why Natural Gradient?, Amari S., Douglas S.C.</a></li>
<li><a href="https://ieeexplore.ieee.org/document/365690" rel="nofollow noreferrer">Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation, Awerbuch, Baruch, Azar, Y.</a></li>
<li><a href="https://proceedings.neurips.cc/paper/2003/file/87682805257e619d49b8e0dfdc14affa-Paper.pdf" rel="nofollow noreferrer">Learning with Local and Global Consistency</a></li>
<li><a href="https://dl.acm.org/doi/10.1145/2556646" rel="nofollow noreferrer">Constraint Satisfaction Problems Solvable by Local Consistency Methods</a></li>
</ol>
<p>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):</p>
<ol>
<li><a href="https://web.archive.org/web/20150105223058/http://www.santafe.edu:80/media/workingpapers/03-09-048.pdf" rel="nofollow noreferrer">Local Evaluation Functions and Global Evaluation
Functions for Computational Evolution, HAN Jing, 2003</a></li>
<li><a href="http://www.santafe.edu/media/workingpapers/02-08-036.pdf" rel="nofollow noreferrer">Emergence from Local Evaluation Function, Han Jing and Cai Qingsheng, 2002</a></li>
</ol>
<p><strong>Abstract</strong> (from 1. above)</p>
<blockquote>
<p>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&amp;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&amp;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.</p>
</blockquote>
<p>Specificaly the paper addresses methods to determnine whether a local function (LEF) is <strong>consistent</strong> with a global function (GEF) and methods to construct consistent LEFs from given GEFs (<strong>Consistency theorem</strong>).</p>
<p><strong>Excerpt from Conclusion section</strong> (from 1. above)</p>
<blockquote>
<p>This paper is just the beginning of LEF&amp;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&amp;GEF to Genetic Algorithms? … It is our intention to study
and attempt to answer all of these questions</p>
</blockquote>

CC BY-SA 4.0
2015-12-17T16:11:04.753Z
2022-07-18T13:24:12.100Z
2022-07-18T13:24:12.100Z
Nikos M.
<p>Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the <a href="http://en.wikipedia.org/wiki/Greedy_algorithm">greedy approach</a>. 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 <a href="http://en.wikipedia.org/wiki/Set_cover_problem">Set Cover Problem</a>. A natural greedy algorithm gives an O(ln n) approximation factor, which is optimal unless P = NP.</p>

<p>Name some natural greedy/local algorithms for NP-hard problems that are provably optimal under suitable complexity theoretic assumptions.</p>

CC BY-SA 2.5
2010-09-14T03:12:14.170Z
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.
Shiva Kintali
CC BY-SA 2.5
2010-09-14T04:01:29.820Z
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.
Kaveh
CC BY-SA 2.5
2010-11-01T12:04:39.167Z
Nicely chosen first sentence.  ;)
AlcubierreDrive
<cc.complexity-theory><lower-bounds><approximation-algorithms><greedy-algorithms><approximation-hardness>
Optimal greedy algorithms for NP-hard problems
Shiva Kintali
# Optimal greedy algorithms for NP-hard problems

(Asked by: username_0 on 2010-09-13)

Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the [greedy approach](http://en.wikipedia.org/wiki/Greedy_algorithm). 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](http://en.wikipedia.org/wiki/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.

**Tags:** cc.complexity-theory, lower-bounds, approximation-algorithms, greedy-algorithms, approximation-hardness

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_2**: Nicely chosen first sentence.  ;)  

---

## 9 answers

### Answer by username_3 on 2010-09-13. Score: 19

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


---

### Answer by username_4 on 2010-09-14. Score: 16

Vertex Cover : The [best constant factor approximation algorithm](http://en.wikipedia.org/wiki/Vertex_cover#Approximate_evaluation) 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](http://en.wikipedia.org/wiki/Vertex_cover#Inapproximability) unless the Unique Games Conjecture is false.

Subhash Khot and Oded Regev, [Vertex cover might be hard to approximate to within 2−ε](http://dx.doi.org/10.1016%2Fj.jcss.2007.06.019), 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.

> **Comments:**
> **username_5**: is the maximal matching algorithm really greedy ?  
> **username_4**: 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.  

---

### Answer by username_6 on 2010-09-13. Score: 11

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


---

### Answer by username_7 on 2010-09-13. Score: 11

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.

> **Comments:**
> **username_8**: 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.  
> **username_7**: Ofcourse, my mistake. Edited the answer to reflect the correction.  

---

### Answer by username_9 on 2010-09-13. Score: 10

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

> **Comments:**
> **username_9**: I think this is the same problem as is @AshwinkumarBV's answer, which I guess was posted while I was typing mine...  

---

### Answer by username_7 on 2010-09-14. Score: 7

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136.1089)


---

### Answer by username_10 on 2012-04-10. Score: 6

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](http://en.wikipedia.org/wiki/Dominating_set) 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](https://www.cs.ucsb.edu/~teo/papers/Ktmm.pdf). Another variant of a $2$-approximation is given by [Hochbaum and Shmoys, A best possible heuristic for the k-center problem, 1985](http://signal.ece.utexas.edu/~vishal/kcenters.pdf).


---

### Answer by username_11 on 2010-09-19. Score: 5

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](http://www.nada.kth.se/~osven/papers/PCmaxFull5Nov.pdf) by Ola Svensson


---

### Answer by username_12 on 2015-12-17. Score: 1

Maybe this would also interest you (adapted from [Methods to translate global constraints to local constraints](https://math.stackexchange.com/questions/1167456/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))](https://www.jmlr.org/papers/volume4/saul03a/saul03a.pdf)
2. [Global optimization using local information with applications to flow control, Bartal, Y.](https://ieeexplore.ieee.org/document/646119)
3. [Why Natural Gradient?, Amari S., Douglas S.C.](http://www.yaroslavvb.com/papers/amari-why.pdf)
4. [Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation, Awerbuch, Baruch, Azar, Y.](https://ieeexplore.ieee.org/document/365690)
5. [Learning with Local and Global Consistency](https://proceedings.neurips.cc/paper/2003/file/87682805257e619d49b8e0dfdc14affa-Paper.pdf)
6. [Constraint Satisfaction Problems Solvable by Local Consistency Methods](https://dl.acm.org/doi/10.1145/2556646)

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](https://web.archive.org/web/20150105223058/http://www.santafe.edu:80/media/workingpapers/03-09-048.pdf)
2. [Emergence from Local Evaluation Function, Han Jing and Cai Qingsheng, 2002](http://www.santafe.edu/media/workingpapers/02-08-036.pdf)

**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


---

