  Navigability of networks, that is the ability to find any given destination
vertex starting from any other vertex, is crucial to their usefulness. In 2000
Kleinberg showed that optimal navigability could be achieved in small-world
networks provided that a special recipe was used to establish long range
connections, and that a greedy algorithm, that ensures that the destination
will be reached, is used. Here we provide an exact solution for the asymptotic
behavior of such a greedy algorithm as a function of the system's parameters.
Our solution enables us to show that the original claim that only a very
special construction is optimal can be relaxed depending on further criteria,
such as, for example, cost minimization, that must be satisfied.
