- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper examines the question of whether there is any information to be gained by looking at the non-commutativity of actions in a local search. The paper describes one artificial example where a signal can be used to improve the move selection. The bulk of the paper is "definitional" type theorems, which result from the definitions themselves, and dont create much new insight.
The main weakness of the paper is its not clear that there is anything to be gained in practice from this exploration. The example used is contrived, and even some of the other examples discussed are odd. The paper itself is not very accessible, being weak on consistent notation, and using many concepts without introducing them.
Critical strengths
The paper investigates a general question about local search: whether non-commutativity of local moves exposes some usable structure that can be exploited in a local search.
Critical weaknesses
The examples used in the paper are all quite artificial, or none of the new mechanisms provide any worth. Without a realistic local search problem that can benefit from the approach there is no discernible advantage from the approach.
Overall Algorithm 1 is an algorithm built to take advantage of the theorems of the paper, but without an non-artificial local search problem that has the required behaviour its hard to argue for its value.
The paper is poorly presented, with lack of definition of much terminology.
l.22. What are NK landscapes?
l.48. What is UCDS?
l.187. Make the pair (i,j) explicit in the definition.
l.210. Its not clear at all what is the purpose of this paragraph. First d_k and f_k are not defined! Please rewrite to make this clearly defined and understandable.
l.258. What is a basin, presumably a subset of X where a one step greedymove policy leads to the same local minima (or plateau). Please define it.
l.277. The measure DX is too tersely defined to be understood. Does the move always result in a difference of 2 (if the edges are considered undirected, or b - a + 1 (if they are considered directed)
l.294. Even here the NK problem is not fully introduced.
l.307. Is their interest on problems with random tables?
Questions for authors
l.134. The approach assumes a function dX, cant we perform local search without such a notion (we just need \Sigma)? Or can we use simple dX where dx(x1,x2) = 0 iff x1 == x2 and 1 otherwise?
l.323. This definition of "Clause-based moves" seems bizarre, and only introduced so that we simply dont have \kappa = 0, which is the case for variable flip moves (the moves actually used by WalkSAT etc). Is their any existing local search SAT approach using such moves, please add a reference.