Additively Decomposable Fitness Functions Abstract
Richard K. Thompson & Alden H. Wright
firstname.lastname@example.org & email@example.com
Computer Science Dept.
The University of Montana
Missoula, MT 59812-1008
We define a class of optimization objective functions over discrete
domains called additively decomposable functions. An
additively decomposable function is a function over several discrete
variables that can be written as a sum of component functions, each
of which depends on only a small number of those variables. The
$N\!K$ fitness landscapes defined by Kauffman are a special case.
If the domain variables have a circular ordering, then under
the adjacent model, we impose the further restriction that
each component function depends on a sequence of adjacent variables
in the ordering. Bandwidth-constrained problems and adjacent $N\!K$
landscapes are special cases. We give a polynomial-complexity dynamic
programming algorithm to optimize adjacent-model additively decomposable
functions, and show that without the adjacency assumption, the
optimization problem is NP-complete.