climbing, typical cost for WSat is low in this region and variance in cost is due to variance For large-backbone instances, the main diculty for local search is to identify the backbone the instance is less costly for WSat to solve. Hence for large-backbone instances, since explanation for the cost peak: Typical cost peaks in the threshold region because of the appearance of many large-backbone instances which are stil l moderately backbone-fragile, fol lowed by the increasing backbone robustness of these instances

## Acknowledgments

university Apes research group http://www.cs.strath.ac.uk/~apes/). We would like to thank the other members of the Apes group, the anonymous reviewers of this and an
