Computing That Serves

Constant-Time gradient information for the MAX-kSAT Landscape


Thursday, December 6, 2012 - 11:00am


Darrell Whitley

Chair of the Computer Science Dept at Colorado State University


Kevin Seppi

Several classic NP-hard problems display "Elementary Landscapes"
on the graph induced by local search operators;  these problems includes TSP, Graph Coloring, Min-Cut/Max-Cut, and Weight Partitioning. Furthermore, it can be shown that MAX-kSAT, Max-Clique, NK-landscapes and Subset Sum can be expressed as a superposition of a small number of elementary landscapes.  Building on these results, one can show that it is possible to compute the exact low-order statistical moments over the generalized Hamming neighborhood for MAX-kSAT problems and for all k-bounded pseudo-Boolean functions. This exact calculation occurs in polynomial time.  We extend this result to show that it is possible to do best-first search in O(1) time per move for MAX-kSAT.  This means we can exactly calculate the location of improving moves without sampling or enumeration of the local search neighborhood.


Darrell Whitley is Chair of the Computer Science Department at Colorado State University.   He served as the Chair of ACM
Sigevo and served on the ACM Sig Governing Board from 2007 to 2011.
He was editor-in-chief of the journal Evolutionary Computation
from 1997 to 2002, and has served on several editorial boards.
He currently serves on the editorial board of Artificial Intelligence.
He has published more than 180 papers with more than 12700 citations.