Algorithms for Approximation and Graph Problems

职务名称：近似和图形问题的算法PI：Richard ColeCCR-0105678本研究关注的是近似解的发现。通常情况下，就所需的时间而言，找到精确解是非常昂贵的，以至于不可行。 然而，“足够好”的相当准确的解决方案可能在更短的时间内获得，因此更实用。 本研究关注的具体问题领域从模式匹配（例如，设计算法来找到DNA序列中的相似和/或重复模式）到本质上难以解决的问题，如旅行推销员问题（相当于找到连接一组城市的最短路线）。 字符串匹配的研究正在考虑新的近似概念，以便设计出比目前可行的更广泛的近似匹配的有效算法;正在研究字符串对之间的搜索和字符串数据库的搜索。 第二部分研究的是NP难问题。 我们正在寻找多成本最短路径问题（例如，与成本包括bothtime和价格），其中一个寻求所有非支配的解决方案，在提高质量的近似旅行推销员问题在飞机上，并在提高theapproximations可获得的广义斯坦纳树问题。

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.