Algorithms for Approximation and Graph Problems

New York University, New York NY

Investigators

Abstract

Title: Algorithms for approximation and graph problems PI: Richard Cole CCR-0105678 This research concerns the finding of approximate solutions. It is often the case that finding exact solutions is vastly too expensive in terms of the time required, to the point of being infeasible. Yet fairly accurate solutions which are "good enough" may be obtainable in a much shorter time, and consequently be more practical. The specific problem domains on which this research focuses range from pattern matching (for example, devising algorithms to find similar and/or repeating patterns in DNA sequences) to intrinsically intractable problems such as the travelling salesman problem (which amounts to finding a shortest route connecting a collection of cities). The research on string matching is considering new notions of approximation so as to devise efficient algorithms for a broader class of approximate matches than is feasible presently; both searches between pairs of strings and against a database of strings are being studied. The second part of our research focuses on NP-hard problems. We are looking at multicost shortest path problems (e.g. with a cost comprising both time and price) in which one seeks all non-dominated solutions, at improving the quality of approximations for the Travelling Salesman Problem in the plane, and also at improving the approximations obtainable for generalized Steiner Tree problems.