Algorithms for Approximation and Graph Problems

点击翻译按钮获取中文摘要

Title: Algorithms for approximation and graph problemsPI: Richard ColeCCR-0105678This research concerns the finding of approximate solutions.It is often the case that finding exact solutions is vastly tooexpensive in terms of the time required, to the point ofbeing infeasible. Yet fairly accurate solutions which are"good enough" may be obtainable in a much shorter time, andconsequently be more practical. The specific problem domainson which this research focuses range from pattern matching(for example, devising algorithms to find similar and/orrepeating patterns in DNA sequences) to intrinsicallyintractable problems such as the travelling salesman problem(which amounts to finding a shortest route connecting acollection of cities). The research on string matching is considering new notionsof approximation so as to devise efficient algorithms for abroader class of approximate matches than is feasible presently;both searches between pairs of strings and against a databaseof strings are being studied. The second part of our researchfocuses on NP-hard problems. We are looking at multicostshortest path problems (e.g. with a cost comprising bothtime and price) in which one seeks all non-dominated solutions,at improving the quality of approximations for the TravellingSalesman Problem in the plane, and also at improving theapproximations obtainable for generalized Steiner Tree problems.