Take the 2-minute tour ×

I find a definition of "exact neighborhood" (the book is online (*1) Definition 1.5 on p.10) confusing.

Do I understand it right that neighborhood that contains the global optimum and no other local optimums/ma is what they call "exact neighborhood" in this book ?

Is this terminology accepted anywhere, or just in this book ?

(*1) http://books.google.com/books?id=u1RmDoJqkF4C&pg=PA10&lr=&hl=iw&source=gbs_toc_r&cad=4#v=onepage&q&f=false Papadimitriou Steiglitz‏ Combinatorial optimization

search in the book: definition 1.5 exact

share|improve this question
I'm not familiar with the terminology but it's not really my area of expertise. It certainly seems like a strange choice of words, given how analogous it is to convexity. –  Andrew D. King Jan 19 '11 at 19:45
All that definition is saying is: Say you have some neighborhood $N$. If every point that is locally optimal for $N$ (i.e., the objective function value at this point is the lowest in the entire neighborhood $N$), is also globally optimal, then the neighborhood $N$ is called exact. For example, if $N$ were the whole space, it would always be exact (because afaik, locally optimal wrt $N$ means, best over entire $N$) –  Suvrit Jan 19 '11 at 20:06

1 Answer 1

up vote 2 down vote accepted

It's important that you understand the definition of a neighborhood used in this book. This is definition 1.3 on page 7. $N$ is not a set but rather a function that maps a solution to the problem to a subset of the entire set of solutions. You can also speak of the neighborhood of a particular solution, s, with respect to $N$, which would be denoted $N(s)$. $N(s)$ is a subset of the set of all solutions.

Your question makes it clear that you don't understand this definition, since you imply that $N$ is a set of solutions.

An example might help. If you're familiar with the 2-opt heuristic for the traveling salesman problem, then "the 2-opt neighborhood" is an example of N, while "the set of tours that can be obtained from the tour T by two-opt moves" is N(T) with respect to the two-opt neighborhood.

This definition makes sense in the context of a local search algorithm. Given a neighborhood N, and an initial solution $s^{0}$, the local search algorithm constructs a sequence of solutions $s^{1}$, $s^{2}$, $\ldots$, by iterating

$s^{n+1}=\arg \min N(s^{n})$

If the neighborhood $N$ is exact, and if the iteration eventually converges to a solution where $s^{n+1}=s^{n}$, then that solution will be globally optimal.

share|improve this answer
Let me just add that I have seen this term used elsewhere within the literature on local search algorithms, although I don't have any references handy. –  Brian Borchers Jan 20 '11 at 0:28

Your Answer


