DIMACS TR: 95-27
A Formal Framework for Evaluating Heuristic Programs
Authors: Lenore Cowen, Joan Feigenbaum and Sampath Kannan
ABSTRACT
We address the question of how one evaluates the usefulness of a heuristic
program on a particular input. If theoretical tools do not allow us to
decide for every instance whether a particular heuristic is fast enough,
might we at least write a simple, fast companion program that makes this
decision on some inputs of interest? We call such a companion program a
timer for the heuristic. Timers are related to program checkers, as defined
by Blum, in the following sense: Checkers are companion programs that check
the correctness of the output produced by (unproven but bounded-time)
programs on particular instances; timers, on the other hand, are companion
programs that attempt to bound the running time on particular instances
of correct programs whose running times have not been fully analyzed. This
paper provides a family of definitions that formalize the notion of a timer
and some preliminary results that demonstrate the utility of these definitions.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-27.ps.gz
DIMACS Home Page