I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm.
Given a real vector $u \in \mathbb{R}^n$, the most similar vector problem is to find a discrete vector $v$ from a bounded integer lattice $L \in \mathbb{Z}^n \cap [-10,10]^n$ that maximizes the cosine similarity between $u$ and $v$. That is,
$$v \in \text{argmax}_{w \in L} \frac{u.w}{\|u\|\|w\|}$$
In an earlier post on MathOverflow, someone proposed solving the most similar vector problem by "zig-zagging" across the lattice. Informally, this is a greedy algorithm that generates a sequence of lattice vectors $w^k$ by starting from the origin and taking steps of length one in the direction of $u$. On the $k^\text{th}$ iteration, the algorithm chooses $w^{k+1}$ as the most similar lattice vector that one unit away from $w^k$ in some dimension. The algorithm terminates in $K$ iterations after we hit the boundary of the lattice in each dimension.
Formally, the "zig-zagging" algorithm can be stated as follows:
INITIALIZATION $$\begin{align} w^0 &\longleftarrow (0,\ldots,0) &\text{(starting point)} \\ d &\longleftarrow \text{sign}(u) \in \{-1,0,1\}^n &\text{(step direction)} \\ \mathcal{J} &\longleftarrow \big\{1,\ldots,n ~\big|~ d_j \neq 0 \big\} &\text{(set of dimensions in which steps can be taken)} \end{align}$$
ALGORITHM
$\text{while } \mathcal{J} \neq \emptyset$
$$\begin{align} j^* &\longleftarrow \text{argmax}_{j \in \mathcal{J}} \frac{u \cdot(w^k + d \cdot e_j)}{\|u\|\|w^k + d \cdot e_j\|} & \text{(step in dimension $j$ that yields $w^{k+1}$ most similar to $u$)} \\ w^{k+1} &\longleftarrow w^k + d \cdot e_{j^*} \\ \mathcal{J} &\longleftarrow \mathcal{J} \setminus \big\{1,\ldots,n ~\big|~ |w_j^{k+1}|=10 \big\} & \text{(remove coordinates at boundary from consideration)} \\ k & \longleftarrow k + 1 \end{align}$$
Here $e_j$ is a unit vector with 1 in the $j^\text{th}$ coordinate and 0 elsewhere.
Once the algorithm terminates, we can use the sequence of generated lattice points $w^1,\ldots,w^K$ to find the most similar vector, $v$ as:
$$v \in \text{argmax}_{k=1,\ldots,K} \frac{u.w^k}{\|u\|\|w^k\|}$$
My question is as follows: Does the zig-zagging algorithm described above produce the most similar vector? If so, how can I prove it? If not, is there a counter example?
