UC San Diego

Local search heuristics provide generalized ways of solving difficult computational problems. In this research we examine a few simple heuristics applied to the Planted Clique Problem, a problem for which there are a number of lower bounds for sophisticated algorithmic techniques. The heuristics run were able to solve the problem at a well known threshold, providing support for the efficacy of simple heuristics.