Files
Abstract
Singular value decomposition's usefulness in graph bisection,genetic algorithms, and information retrieval is studied. An infor-mation retrieval theorem about latent semantic indexing (LSI) ispresented in detail. Several theorems are proved concerning bi-section size guarantees when performing spectral bisection withthe singular value decomposition of adjacency matrices of certaingraphs. In addition, singular value decomposition is used in manyways to enhance a genetic algorithm's performance.Highlights of the results include:Clarification of a well known LSI theorem, with counterexam-ples.Improvement of heuristics for finding the minimum bisectionof a graph.Minimum bisection guarantees for graphs with a certain struc-tures using a new proof strategy.Empirical evidence that multiple eigenvectors can be useful inspectral bisection.Several novel applications of singular value decomposition ingenetic algorithms.