Andrew M. Sutton

Ph.D. Candidate
Department of Computer Science
242 Computer Science Building
1100 Center Avenue Mall
Colorado State University
Fort Collins, CO 80523
(970) 491-7016
sutton at cs.colostate.edu

Teaching

CS 301 - Foundations of Computer Science - Fall 2009

Research

Algorithms for search lie at the heart of most artificial intelligence research. Informally, a search algorithm moves through some configuration space to locate states that satisfy some value (or cost) criterion. My dissertation research involves the study of the topological properties of search spaces and how they affect dynamical behavior of search algorithms for solving combinatorial optimization problems.

Combinatorial optimization problems typically are intractable to solve exactly (NP-Hard) and, in many cases, hard to approximate (APX-Hard). This makes the application of search to such problems especially interesting. The study of properties that make a problem difficult (or easy) for search has deep roots in theoretical computer science, complex systems science, and even statistical mechanics.

I am currently involved with the SCHEDuling research group here at CSU. We are funded by a grant from the Discrete Mathematics and Optimization Program of the Air Force Office of Scientific Research.

Publications

• A. M. Sutton, A. E. Howe, and L. D. Whitley, A Theoretical Analysis of the k-Satisfiability Search Space, In Proceedings of SLS 2009, Brussels, Belgium, September 2009. Published in Lecture Notes in Computer Science Vol. 5752, (2009) pp. 46-60.
  [Second runner-up for Best Paper Award]
  [ps.gz] [pdf]
• A. M. Sutton, A. E. Howe, and L. D. Whitley, Estimating Bounds on Expected Plateau Size in MAXSAT Problems, In Proceedings of SLS 2009, Brussels, Belgium, September 2009. Published in Lecture Notes in Computer Science Vol. 5752, (2009) pp. 31-45.
  [ps.gz] [pdf]
• A. M. Sutton, L. D. Whitley, and A. E. Howe, A Polynomial Time Computation of the Exact Correlation Structure of k-Satisfiability Landscapes, In Genetic and Evolutionary Computation Conference (GECCO-09), Montreal, Canada, July 2009.
  [ps.gz] [pdf] [slides]
• L. D. Whitley and A. M. Sutton, Partial Neighborhoods of Elementary Landscapes, In Genetic and Evolutionary Computation Conference (GECCO-09), Montreal, Canada, July 2009.
  [ps.gz] [pdf]
• M. Lunacek, D. Whitley, and A. Sutton, The Impact of Global Structure on Search, In Proceedings of the 10th Conference on Parallel Problem Solving from Nature (PPSN-08), Dortmund, Germany, September 2008.
  [Awarded Best Student Paper]
  [ps.gz] [pdf]
• L. D. Whitley, A. M. Sutton, and A. E. Howe, Understanding Elementary Landscapes, In Genetic and Evolutionary Computation Conference (GECCO-08), Atlanta, GA.
  [ps.gz] [pdf]
• A. M. Sutton, A. E. Howe, and L. D. Whitley, Using Adaptive Priority Weighting to Direct Search in Probabilistic Scheduling, In International Conference on Automated Planning and Scheduling (ICAPS-07), Providence, RI.
  [ps.gz] [pdf]
• A. M. Sutton, M. Lunacek, and L. D. Whitley, Differential Evolution and Non-separability: Using selective pressure to focus search, Genetic and Evolutionary Computation Conference (GECCO-07), London, England.
  [ps.gz] [pdf]
• J. Smith, L. D. Briceno, A. A. Maciejewski, H. J. Siegel, D. Janovy, T. Renner, J. Ladd, A. Sutton, S. Govindasamy, A. Alqudah, R. Dewri, P. Prakash, V. Shestak, Measuring the Robustness of Resource Allocations in a Stochastic Dynamic Environment, International Parallel and Distributed Processing Symposium (IPDPS 2007), Long Beach, CA.
  [ps.gz] [pdf]
• A. M. Sutton, L. D. Whitley, M. Lunacek, and A. Howe, PSO and Multifunnel Landscapes: How cooperation might limit exploration, Genetic and Evolutionary Computation Conference (GECCO-06), Seattle, WA.
  [Nominated for Best Paper]
  [ps.gz] [pdf]
• A. M. Sutton, A. Howe, and L. D. Whitley, Spacetrack: Trading-off Quality and Utilization in Oversubscribed Schedules, International Conference on Automated Planning and Scheduling (ICAPS-06) English Lake District, UK.
  [ps.gz] [pdf]