Abstract
One of the approaches for the nearest neighbor search problem is to build a network which nodes correspond to the given set of indexed objects. In this case the search of the closest object can be thought as a search of a node in a network. A procedure in a network is called decentralized if it uses only local information about visited nodes and its neighbors. Networks, which structure allows efficient performing the nearest neighbour search by a decentralised search procedure started from any node, are of particular interest especially for pure distributed systems. Several algorithms that construct such networks have been proposed in literature. However, the following questions arise: "Are there network models in which decentralised search can be performed faster?"; "What are the optimal networks for the decentralised search?"; "What are their properties?". In this paper we partially give answers to these questions. We propose a mathematical programming model for the problem of determ