# Minimal Conditions for Beneficial Neighbourhood Search and Local Descent

arXiv: https://arxiv.org/abs/2411.05263 · HTML: https://mlsanity.com/paper/2411.05263/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 23 references that are in the map.
- First posted on arXiv 8 Nov 2024.

## Abstract (arXiv)

This paper investigates what properties a neighbourhood requires to support beneficial local search. We show that neighbourhood locality, and a reduction in cost probability towards the optimum, support a proof that search among neighbours is more likely to find an improving solution in a single search step than blind search. This is the first paper to introduce such a proof. The concepts underlying these properties are illustrated on a satisfiability problem class, and on travelling salesman problems. Secondly, for a given cost target t, we investigate a combination of blind search and local descent termed local blind descent, and present various conditions under which the expected number of steps to reach a cost better than t using local blind descent, is proven to be smaller than with blind search. Experiments indicate that local blind descent, given target cost t, should switch to local descent at a starting cost that reduces as t approaches the optimum.