Second Order Partial Derivatives for NK-landscapes

Local search methods based on explicit neighborhood enumeration require at least O(n) time to identify all possible improving moves. For k-bounded pseudo-Boolean optimization problems, recent approaches have achieved O(k(2) * 2(k)) runtime cost per move, where n is the number of variables and k is the number of variables per sub-function. Even though the bound is independent of n, the complexity per move is still exponential in k. In this paper, we propose a second order partial derivatives-based approach that executes first-improvement local search where the runtime cost per move is time polynomial in k and independent of n. This method is applied to NK-landscapes, where larger values of k may be of particular interest.