|
NeuroCOLT
Technical Report NC-TR-97-038
Using
Computational Learning Strategies as a Tool for Combinatorial
Optimization
Andreas
Birkendorf and Han Ulrich Simon
Universität Dortmund
Germany
Abstract
In this paper, we describe how a basic strategy from computational
learning theory can be used to attach a class of NP-hard combinatorial
optimization problems. It turns out that the learning strategy can
be used as an iterative booster: given a solution to the combinatorial
problem, we will start an efficient simulation of a learning algorithm
which as a ``good chance'' to output an improved solution. This
boosting technique is a new and surprisingly simple application of
an existing learning strategy. It yields a novel heuristic approach
to attach NP-hard optimization problems. It does not apply to each
combinatorial problem, but we are able to exactly formalize some sufficient
conditions. The new technique applies, for instance, to the problems
of minimizing a deterministic finite automaton relative to a
given domain, the analogous problem for ordered binary decision
diagrams, and to graph colouring.
Download Compressed
Postscript
Title Page
|