Abstract
A local minimum of a matrix is a cell whose value is smaller than those of its four adjacent cells. For an n × n square matrix, we find a local minimum with at most 2.554n queries, and prove a lower bound of 2n queries required by any method. For a different neighborhood corresponding to the eight possible moves of a chess king, we prove upper and lower bounds of3n + O(log n) and 2n, respectively.
Original language | English |
---|---|
Pages (from-to) | 131-153 |
Number of pages | 23 |
Journal | Discrete Applied Mathematics |
Volume | 43 |
Issue number | 2 |
DOIs | |
State | Published - 19 May 1993 |
Keywords
- Local optimum
- graph
- grid
- local search
- matrix
- saddle point