Finding a Local Minimum of $G$: Algorithm & Analysis

[evinda]

Hello! (Wave)

A $m \times m$ grid is a graph of which the vertices are ordered pairs of natural numbers $(n_1, n_2)$ with $1 \leq n_1 \leq m$ and $1 \leq n_2 \leq m$.
Two vertices $(k_1,k_2)$ and $(k_3,k_4)$ are neighbors iff $|k_1-k_2|+|k_3-k_4|=1$.
We suppose that a unique number $y_w$ is assigned to each vertex.
A vertex $w$ is local minimum if $y_w<y_u$ for all the neighbors $u$ of $w$.

Given such a graph and an assignement of natural numbers at the vertices, we want to find a local minimum of $G$.

1.w<-(1,1)
2.while there is a neighbor u of w with y_u<y_w
3.   let u be the neighbor of w with smallest y_u
4. w<-u
5.end while
6.return w

How could we show that the above algorithm always returns a local mimum of $G$?

How many time does the algorithm require in the worst case?
Does it require $\Theta(m^2)$ because it could go through all the vertices? Or am I wrong? (Thinking)

 

[I like Serena]

Hi! (Smile)

How could we show that the above algorithm always returns a local mimum of $G$?

What is the condition of the loop?
So which condition must be true when the loop finishes? (Wondering)

How many time does the algorithm require in the worst case?
Does it require $\Theta(m^2)$ because it could go through all the vertices? Or am I wrong? (Thinking)

The worst theoretical case could conceivable be if it could go through all vertices, giving us $O(m^2)$.
But that won't happen, since it would always be possible to take a shortcut. (Worried)

Can you find a grid with a valid path of, say, $\frac 12 m^2$ steps? (Wondering)

 

[evinda]

Hi! (Smile)
What is the condition of the loop?
So which condition must be true when the loop finishes? (Wondering)

This is the condition of the loop: [m]while there is a neighbor u of w with y_u<y_w[/m].

So when the loop finishes, $u$ will have the smallest natural number from the nodes that we have visited. We start from a node, look at its neighbor $v$, then at the neighbor of $v$ and so on.. Or am I wrong? (Thinking)

The worst theoretical case could conceivable be if it could go through all vertices, giving us $O(m^2)$.
But that won't happen, since it would always be possible to take a shortcut. (Worried)

Can you find a grid with a valid path of, say, $\frac 12 m^2$ steps? (Wondering)

Can $|k_1-k_2|+|k_3-k_4|=1$ only hold if $k_2=k_1 \pm 1, k_3= \pm k_4$ or $k_4=k_3 \pm 1, k_1= \pm k_2$?
Or could the equality also hold under other conditions ? (Thinking)

 

[I like Serena]

This is the condition of the loop: [m]while there is a neighbor u of w with y_u<y_w[/m].

So when the loop finishes, $u$ will have the smallest natural number from the nodes that we have visited. We start from a node, look at its neighbor $v$, then at the neighbor of $v$ and so on.. Or am I wrong? (Thinking)

Yes, we follow the neighbors down.

And when the loop finishes, the negation of the condition must be true:
[m]NOT (there is a neighbor u of w with y_u<y_w)[/m] = [m]every neighbor u of w has y_u >= y_w[/m]

Is equality possible? (Wondering)

Can $|k_1-k_2|+|k_3-k_4|=1$ only hold if $k_2=k_1 \pm 1, k_3= \pm k_4$ or $k_4=k_3 \pm 1, k_1= \pm k_2$?
Or could the equality also hold under other conditions ? (Thinking)

You've got it right. (Nod)

 

[evinda]

Yes, we follow the neighbors down.

And when the loop finishes, the negation of the condition must be true:
[m]NOT (there is a neighbor u of w with y_u<y_w)[/m] = [m]every neighbor u of w has y_u >= y_w[/m]

Is equality possible? (Wondering)

No, equality isn't possible because of the fact that a unique number represents each node, right? (Thinking)So can we just say that the above negation has to hold and thus the algorithm returns always a local minimum or do we have to explain it further? (Thinking)

You've got it right. (Nod)

(Happy)

The worst theoretical case could conceivable be if it could go through all vertices, giving us $O(m^2)$.
But that won't happen, since it would always be possible to take a shortcut. (Worried)

Can you find a grid with a valid path of, say, $\frac 12 m^2$ steps? (Wondering)

I tried to make an example:View attachment 4370So we go only through the vertices of the form $(i,i), (j,j+1)$ and $(k,k-1)$, right? (Thinking)

 

[I like Serena]

Can $|k_1-k_2|+|k_3-k_4|=1$ only hold if $k_2=k_1 \pm 1, k_3= \pm k_4$ or $k_4=k_3 \pm 1, k_1= \pm k_2$?
Or could the equality also hold under other conditions ? (Thinking)

Wait! (Wait)

It should be: $k_2=k_1 \pm 1, k_3= k_4$ or $k_4=k_3 \pm 1, k_1= k_2$.

No, equality isn't possible because of the fact that a unique number represents each node, right? (Thinking)

So can we just say that the above negation has to hold and thus the algorithm returns always a local minimum or do we have to explain it further? (Thinking)

Indeed, so if the while-loop ends we are guaranteed to have found a local minimum.

That leaves the question: does the while-loop always end? (Wondering)

I tried to make an example:

So we go only through the vertices of the form $(i,i), (j,j+1)$ and $(k,k-1)$, right? (Thinking)

Sorry, I don't understand. (Doh)

Can you explain it further? (Wondering)

 

[evinda]

Wait! (Wait)

It should be: $k_2=k_1 \pm 1, k_3= k_4$ or $k_4=k_3 \pm 1, k_1= k_2$.

Oh yes, right... (Nod)

Indeed, so if the while-loop ends we are guaranteed to have found a local minimum.

That leaves the question: does the while-loop always end? (Wondering)

No,it doesn't.. If we have found the local minimum, we will visit again all its neighbors and conclude that the former is represented by the smallest natural number and then we will continue with exactly the same procedure, right? (Thinking)

Sorry, I don't understand. (Doh)

Can you explain it further? (Wondering)

I noticed that we will not visit all the nodes, but only the ones of the form $(i,i), (j,j-1), (k,k+1), i,j,k \in \mathbb{N}$..
Isn't it like that?
If so, do we find the time complexity, using this fact? (Thinking)

 

[I like Serena]

No,it doesn't.. If we have found the local minimum, we will visit again all its neighbors and conclude that the former is represented by the smallest natural number and then we will continue with exactly the same procedure, right? (Thinking)

Huh?
If we have found a local minimum, the condition of the while-loop becomes false and the algorithm terminates.

I noticed that we will not visit all the nodes, but only the ones of the form $(i,i), (j,j-1), (k,k+1), i,j,k \in \mathbb{N}$..
Isn't it like that?
If so, do we find the time complexity, using this fact? (Thinking)

Suppose we want the path to be (1,1) - (1,2) - (1,3) - (1,4) - (2,4) - (3,4) - (4,4) - (4,3) - (4,2) - (3,2).
Can we find grid values so that this path will be taken? (Wondering)

 

[evinda]

Huh?
If we have found a local minimum, the condition of the while-loop becomes false and the algorithm terminates.

Oh yes, right... (Tmi)

So does it suffice to justify that the algorithm returns always a local minimum as follows?The while-loop is executed while there is a neighbor [m]u[/m] of [m]w[/m] with [m]y_u<y_w[/m]. So when the loop finishes, the negation of the condition must be true:
[m]NOT (there is a neighbor u of w with y_u<y_w)[/m] = [m]every neighbor u of w has y_u >= y_w[/m].
Equality isn't possible because of the fact that a unique number represents each node.

So after the termination it will hold that every neighbor [m]u[/m] of [m]w[/m] has [m]y_u > y_w[/m], which is the condition that has to hold so that $w$ is a local minimum.

If we have found a local minimum, the condition of the while-loop becomes false and the algorithm terminates.

Suppose we want the path to be (1,1) - (1,2) - (1,3) - (1,4) - (2,4) - (3,4) - (4,4) - (4,3) - (4,2) - (3,2).
Can we find grid values so that this path will be taken? (Wondering)

I thought that after a node of the form $(i,i)$, only a node of the form $(j,j-1)$ or $(j,j+1)$ can follow.

For example, in this case:View attachment 4373

the neighbor of $(1,1)$ with the smallest $y_w$ is $(1,2)$ and then the neighbors of $(1,2)$ will be $(1,1), (2,2), (3,3), (4,4)$ and from these the node with the smallest $y_w$ is $(2,2)$.
Am I wrong? (Thinking)

 

[I like Serena]

The while-loop is executed while there is a neighbor [m]u[/m] of [m]w[/m] with [m]y_u<y_w[/m]. So when the loop finishes, the negation of the condition must be true:
[m]NOT (there is a neighbor u of w with y_u<y_w)[/m] = [m]every neighbor u of w has y_u >= y_w[/m].
Equality isn't possible because of the fact that a unique number represents each node.

So after the termination it will hold that every neighbor [m]u[/m] of [m]w[/m] has [m]y_u > y_w[/m], which is the condition that has to hold so that $w$ is a local minimum.

If we have found a local minimum, the condition of the while-loop becomes false and the algorithm terminates.

You need one thing more: the certainty that the while-loop will terminate.
What if the condition of the while-loop never becomes false and we keep going in an infinite loop? (Doh)

I thought that after a node of the form $(i,i)$, only a node of the form $(j,j-1)$ or $(j,j+1)$ can follow.

For example, in this case:

the neighbor of $(1,1)$ with the smallest $y_w$ is $(1,2)$ and then the neighbors of $(1,2)$ will be $(1,1), (2,2), (3,3), (4,4)$ and from these the node with the smallest $y_w$ is $(2,2)$.
Am I wrong? (Thinking)

Two vertices $(k_1,k_2)$ and $(k_3,k_4)$ are neighbors iff $|k_1-k_2|+|k_3-k_4|=1$.

Can $|k_1-k_2|+|k_3-k_4|=1$ only hold if $k_2=k_1 \pm 1, k_3= k_4$ or $k_4=k_3 \pm 1, k_1= k_2$?

Hmm, I'm only now noticing that there is something odd with the definition of neighbors.
I expected that $(a,b)$ and $(x,y)$ would be neighbors iff $|a-x|+|b-y|=1$.
That is, iff $(x,y)$ is one of $(a-1,b),(a,b-1),(a+1,b),(a,b+1)$.
This is pretty standard. (Thinking)

Can you check if there's a typo in there? (Wondering)
Because imo the definition as it is, is kind of nonsensical.
I suspect "iff $|k_1-k_3|+|k_2-k_4|=1$" was intended.
And if it were intended as is, I'd expect some kind of additional text confirming that's it is supposed to be unusual.

 

[evinda]

You need one thing more: the certainty that the while-loop will terminate.
What if the condition of the while-loop never becomes false and we keep going in an infinite loop? (Doh)

We are looking for all the neighbors of w and pick this with the smallest y_u, then we pick the latter as the new u and continue the same procedure as above. If we have reached to a vertex w that has no neighbors i with y_w>y_i, the condition of the while-loop will not be true and so the algorithm will terminate.

Is it right? How could we explain it more formally? (Thinking)

Hmm, I'm only now noticing that there is something odd with the definition of neighbors.
I expected that $(a,b)$ and $(x,y)$ would be neighbors iff $|a-x|+|b-y|=1$.
That is, iff $(x,y)$ is one of $(a-1,b),(a,b-1),(a+1,b),(a,b+1)$.
This is pretty standard. (Thinking)

Can you check if there's a typo in there? (Wondering)
Because imo the definition as it is, is kind of nonsensical.
I suspect "iff $|k_1-k_3|+|k_2-k_4|=1$" was intended.
And if it were intended as is, I'd expect some kind of additional text confirming that's it is supposed to be unusual.

It says that two vertices $(k_1,k_2)$ and $(k_2,j_2)$ are neighbors iff $|k_1-k_2|+|j_1-j_2|=1$.

I thought that it was a typo, that's why I wrote it as I did.. (Blame)

So it will be right as you say.. (Nod)

 

[I like Serena]

We are looking for all the neighbors of w and pick this with the smallest y_u, then we pick the latter as the new u and continue the same procedure as above. If we have reached to a vertex w that has no neighbors i with y_w>y_i, the condition of the while-loop will not be true and so the algorithm will terminate.

Is it right? How could we explain it more formally? (Thinking)

That doesn't quite catch the real reason that the while-loop will terminate.
Suppose we had an infinite number of vertices with no local minimum, then the while-loop would go on forever. (Worried)
Or suppose we could back to a node we had already visited, then we would also be stuck in an infinite loop. (Doh)

I'd say something like:

There is only a finite number of vertices.
Since in each iteration we move to a node with a strictly lower value (due to the uniqueness of values), we can only iterate a finite number of times. Therefore the while-loop is guaranteed to terminate. (Nerd)

It says that two vertices $(k_1,k_2)$ and $(k_2,j_2)$ are neighbors iff $|k_1-k_2|+|j_1-j_2|=1$.

I thought that it was a typo, that's why I wrote it as I did.. (Blame)

So it will be right as you say.. (Nod)

Ah ok... (Happy)

 

[evinda]

That doesn't quite catch the real reason that the while-loop will terminate.
Suppose we had an infinite number of vertices with no local minimum, then the while-loop would go on forever. (Worried)
Or suppose we could back to a node we had already visited, then we would also be stuck in an infinite loop. (Doh)

I'd say something like:

There is only a finite number of vertices.
Since in each iteration we move to a node with a strictly lower value (due to the uniqueness of values), we can only iterate a finite number of times. Therefore the while-loop is guaranteed to terminate. (Nerd)

So can we show as follows that the algorithm always returns a local minimum?The while-loop is executed while there is a neighbor [m]u[/m] of [m]w[/m] with [m]y_u<y_w[/m]. So when the loop finishes, the negation of the condition must be true:
[m]NOT (there is a neighbor u of w with y_u<y_w)[/m] = [m]every neighbor u of w has y_u >= y_w[/m].
Equality isn't possible because of the fact that a unique number represents each node.

So after the termination it will hold that every neighbor [m]u[/m] of [m]w[/m] has [m]y_u > y_w[/m], which is the condition that has to hold so that $w$ is a local minimum.

There is only a finite number of vertices.
Since in each iteration we move to a node with a strictly lower value (due to the uniqueness of values), we can only iterate a finite number of times. Therefore the while-loop is guaranteed to terminate.

Also, I found a graph at which we go through all the vertices, in order to find the local minimum:View attachment 4374Or have I done something wrong and it isn't like that? (Thinking)

 

[I like Serena]

So can we show as follows that the algorithm always returns a local minimum?

Seems fine to me. (Nod)

Also, I found a graph at which we go through all the vertices, in order to find the local minimum:
Or have I done something wrong and it isn't like that? (Thinking)

Good! (Smile)

Note that we're not moving through all the vertices, but all vertices do get examined.
Actually, we move through $\frac 12 m^2$ vertices, and at each step we examine $2-4$ neighbors.
That makes it indeed $\Theta(m^2)$. (Mmm)

Can you formulate a worst case path for which we can always find a grid for which is the case? (Wondering)

 

[evinda]

Seems fine to me. (Nod)

Nice! (Happy)

Good! (Smile)

Note that we're not moving through all the vertices, but all vertices do get examined.
Actually, we move through $\frac 12 m^2$ vertices, and at each step we examine $2-4$ neighbors.
That makes it indeed $\Theta(m^2)$. (Mmm)

Because of the fact that we can't go back, we can just go through vertices that we haven't visited yet.. Right? (Thinking)

Can you formulate a worst case path for which we can always find a grid for which is the case? (Wondering)

We have the worst case if all the lines of the graph , except the last one,are sorted in decreasing order.. Or am I wrong? (Worried)

 

[evinda]

Also how could we solve the problem in linear time, assuming that $m$ is a power of $2$? (Thinking)

 

[I like Serena]

Because of the fact that we can't go back, we can just go through vertices that we haven't visited yet.. Right? (Thinking)

We have the worst case if all the lines of the graph , except the last one,are sorted in decreasing order.. Or am I wrong? (Worried)

I'm afraid not.

In that case we would make $m-1$ steps to the right and $m-1$ steps down in some arbitrary order, and finally $m-1$ steps left.
This would be O(3m). (Sweating)

Also how could we solve the problem in linear time, assuming that $m$ is a power of $2$? (Thinking)

Then we should be able to use a bisection algorithm.

I think we could examine the corners, select the quadrant that has the lowest corner, and repeat. (Thinking)

 

[evinda]

I was wondering why we move through $\frac{1}{2}m^2$ vertices. Because of the fact that we just move though the vertices that we haven't visited yet? (Thinking)

I'm afraid not.

In that case we would make $m-1$ steps to the right and $m-1$ steps down in some arbitrary order, and finally $m-1$ steps left.
This would be O(3m). (Sweating)

So in order to have the worst case, does the first line have to be sorted in decreasing order, the second line in increasing order, the third in decreasing and so on? Or am I wrong? (Thinking)

Then we should be able to use a bisection algorithm.

I think we could examine the corners, select the quadrant that has the lowest corner, and repeat. (Thinking)

With examining the corners, do you mean for example in our case that we find the smaller value from the values of $(1,1), (1,4), (4,1), (4,4)$ ? Or have I understood it wrong? (Worried)

 

[I like Serena]

I was wondering why we move through $\frac{1}{2}m^2$ vertices. Because of the fact that we just move though the vertices that we haven't visited yet? (Thinking)

The grid is too small to show the pattern.
But if we move through every other line, we have $m$ vertices in each line and $\frac 12 m$ lines that we move through. (Thinking)

So in order to have the worst case, does the first line have to be sorted in decreasing order, the second line in increasing order, the third in decreasing and so on? Or am I wrong? (Thinking)

Suppose so, which path would we get? (Wondering)

With examining the corners, do you mean for example in our case that we find the smaller value from the values of $(1,1), (1,4), (4,1), (4,4)$ ? Or have I understood it wrong? (Worried)

Let's make the grid 1 step larger.
Then we have $(0,0), (0,4), (4,0), (4,4)$ as corners.
Suppose $(0,4)$ is the smallest corner, then we pick $(0,2), (0,4), (2,2), (2,4)$ for the next iteration. (Thinking)

 

[evinda]

The grid is too small to show the pattern.
But if we move through every other line, we have $m$ vertices in each line and $\frac 12 m$ lines that we move through. (Thinking)

So since we move in each line through $\frac 12 m$ vertices, the time complexity of the algorithm is $\Theta(m \cdot \frac{1}{2}m^2)=\Theta(m^2)$? Or have I understood it wrong? (Thinking)

Suppose so, which path would we get? (Wondering)

At the following graph, the most of the vertices are sorted and we move through $11=O(4^2)$ vertices, or not? (Thinking)

View attachment 4377

Let's make the grid 1 step larger.
Then we have $(0,0), (0,4), (4,0), (4,4)$ as corners.
Suppose $(0,4)$ is the smallest corner, then we pick $(0,2), (0,4), (2,2), (2,4)$ for the next iteration. (Thinking)

View attachment 4378

How can we be sure that the local minimum is in the subgraph with corners $(0,2), (0,4), (2,2), (2,4)$? At the above graph, the local minimum is $(3,3)$, that is not in this subgraph (assuming that its neighbors have no smaller values).. Or am I wrong? (Worried)

 

[I like Serena]

So since we move in each line through $\frac 12 m$ vertices, the time complexity of the algorithm is $\Theta(m \cdot \frac{1}{2}m^2)=\Theta(m^2)$? Or have I understood it wrong? (Thinking)

At the following graph, the most of the vertices are sorted and we move through $11=O(4^2)$ vertices, or not? (Thinking)

I think we would only move through 5 vertices before we stop. (Sweating)

But we can get to a path that looks like:

[TEXTDRAW]xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx[/TEXTDRAW]
(Wasntme)

How can we be sure that the local minimum is in the subgraph with corners $(0,2), (0,4), (2,2), (2,4)$? At the above graph, the local minimum is $(3,3)$, that is not in this subgraph (assuming that its neighbors have no smaller values).. Or am I wrong? (Worried)

You are right. It won't work. (Worried)

 

[evinda]

I think we would only move through 5 vertices before we stop. (Sweating)

But we can get to a path that looks like:

[TEXTDRAW]xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxx[/TEXTDRAW]
(Wasntme)

At this case, the natural number that represents the vertex in line 2, is smaller than the one of its neighbors from above and from the ones next to it, but greater than the natural numbers that represent the neighbors that are below it. Or am I wrong? (Thinking)

You are right. It won't work. (Worried)

Could you give me a hint what else we could do? (Thinking)

 

[I like Serena]

At this case, the natural number that represents the vertex in line 2, is smaller than the one of its neighbors from above and from the ones next to it, but greater than the natural numbers that represent the neighbors that are below it. Or am I wrong? (Thinking)

I don't understand what you mean. (Worried)

I was thinking of a grid like:
[textdraw]35 34 33 32 31 30 29 28
99 99 99 99 99 99 99 27
19 20 21 22 23 24 25 26
18 99 99 99 99 99 99 99
17 16 15 14 13 12 11 10
99 99 99 99 99 99 99 9
1 2 3 4 5 6 7 8
99 99 99 99 99 99 99 99[/textdraw]
where each 99 should be replaced by an arbitrarily big distinct number. (Wasntme)

Could you give me a hint what else we could do? (Thinking)

Suppose we divide the square in two and find the minimum on their line of separation.
That means examining $m$ vertices.
Then peek at its 2 neighbors.
If they are both bigger we have found a minimum.
Otherwise we divide the lower rectangle into 2 equal parts and repeat. (Thinking)