MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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) Papadimitriou Steiglitz‏ Combinatorial optimization

search in the book: definition 1.5 exact

share|cite|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
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|cite|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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.