We study different versions of local search on variable orderings. In contrast to previous work that defined the local neighborhood of an ordering as all orderings that can be reached via one operation, we consider parameterized local search [1]}, [2]}, [3]}, [4]}, [5]}. Here, one sets a parameter \(r\)  and aims to find a better network that can be reached via at most \(r\)  modifications of the ordering. The hope is that, by considering such a larger neighborhood, one may avoid being stuck in a bad local optimum. We consider three different kinds of operations in this work. We first study insertions, where one may move one variable to an arbitrary position in the ordering and swaps where two arbitrary variables may exchange their positions. Recall that local search strategies based on one insertion have been studied previously [6]}, [7]}. We observe that the local search problem can be solved in polynomial time for both variants if \(r\)  is constant. The degree of the polynomial, however, depends on \(r\) . We show that, under widely accepted complexity-theoretic assumptions, this dependence cannot be avoided. Afterwards, we study inversions, which are swaps of adjacent vertices. Our main result is an algorithm with running time \(2^{\mathcal {O}(\sqrt{r}\log r)}\cdot \text{\normalfont {poly}}(|I|)\)  for deciding for a given variable ordering, whether there is a better ordering that can be reached via at most \(r\)  inversions. The distance that measures the minimum number of inversions needed to transform one ordering in another is also known as the Kendall tau distance as it is an adaption of Kedall tau rank correlation [8]}. We then introduce a new distance that we call inversion-window distance. Intuitively, given an ordering \(\tau \)  we find an ordering \(\tau ^{\prime }\)  that has inversion-window distance at most \(r\)  by partitioning \(\tau \)  into multiple windows of consecutive vertices and performing up to \(r\)  inversions inside each window. This new distance extends the number of inversions in the following sense: Given a search radius \(r\) , the search space for orderings with inversion-window distance \(r\)  is potentially larger than the number of orderings one can obtain with at mots \(r\)  inversions. We provide an algorithm with running time \(2^{\mathcal {O}(\sqrt{r}\log r)}\cdot \text{\normalfont {poly}}(|I|)\)  that decides for a given ordering, whether there is a better ordering that has inversion-window distance at most \(r\) . An overview of the distances studied in this work is shown in Figure REF .
