Database Learning: a Method for Empirical Algorithm Design.
Mark Goldberg, David L. Hollinger · 1997
The paper describes a novel method for empirical algorithm design called database learning, and presents experimental results of applying the strategy to designing algorithms for the problem of constructing a maximum independent set in a given graph. 1. Introduction Backtracking is an algorithmic paradigm that can be used for the majority of combinatorial optimization problems. It is very well known, though, that the strategy is inefficient for even moderate-size inputs. However, experiments show ([1],[5]) that for many problems, given a class of inputs, optimal solutions to the instances from the class are "located" in an area which is significantly smaller than the full search tree. Thus, "learning" the area containing solutions---the search area of the class---may lead to efficient backtracking-based algorithms for a given class of inputs. In this paper, we present learning strategies for determining search areas of combinatorial optimization problems. Our model of learning is a v...