Resolving Anomalies in Approximation Algorithms

解决近似算法中的异常

• 批准号: 0514628
• 负责人: David Williamson
• 金额: $ 20.44万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514628&HistoricalAwards=false
• 关键词: Resolving; Anomalies; Approximation; Algorithms

Many problems in combinatorial optimization are NP-hard, and unlikely to have efficient algorithms to find the optimal solution. These include multitudes of problems that arise in practice in industry, including locating facilities to service customer demands, scheduling service personnel to make onsite repairs, dispatching vehicles, constructing low-cost networks with specific connectivity properties, routing wires on chips, and many, many others. The typical approaches for solving these problems are to design some heuristic that in practice provides solutions that are good enough, or, if enough time and resources are available and an optimal solution is sufficiently valuable, to designan exhaustive search algorithm to find the optimal solution.In order to mathematically ground the study of heuristics, computer scientists have considered approximation algorithms. These are efficient, polynomial-time algorithms that produce solutions that are provably close in value to the optimal solution. In particular, an _-approximation algorithm produces a solution whose value is within a factor of _ of the value of an optimal solution. The parameter _ is sometimes called the performance guarantee of the algorithm. To prove that the algorithm produces a near-optimal solution, a bound on the optimal value must be used. This bound is often a quantity that can be computed efficiently on its own, and in many interesting cases is based on a linear programming relaxation of the problem. When a polynomial-time computable bound, such as a linear programming bound, is used to prove a strong performance guarantee, this also has implications for practitioners who solve problems to optimality using exhaustive search, since a strong bound is useful in quickly pruning the search space.The goal of the proposal is to study some anomalies in the current state of knowledge of approximation algorithms, since as in other areas of science, consideration of anomalies leads most quickly to new advances. Several known approximation algorithms use as their bound quantities that are not polynomial-time computable; or, even if polynomial-time computable, are difficult to show apriori are bounds on the problem being considered. Included in the study are problems of locating facilities that can serve a bounded amount of customer demand (the capacitated facility location problem), designing low-cost networks (the Steiner tree problem), and the routing of vehicles to minimize the average time at which a vehicle arrives at a customer (the minimumlatency problem). The goal of the research is to show that these algorithms can be restated in terms of polynomial-time computable bounds, and, as often as possible, bounds involving linear programming relaxations.Intellectual merit: Significant methodological innovations will likely be needed to resolvethese issues. Additionally, the PI expects to find simpler, better, more general, and more practical approximation algorithms as a result of this research. Furthermore, if polynomial-time computable bounds can be found for some of these problems, it will lead to better exhaustive search algorithms for finding the optimal solution for these problems. The PI is one of the leaders in the field of approximation algorithms and has an extensive track record of finding new methods and improved algorithms.Broader impact: The PI will train of graduate researchers in the broader area of combinatorial optimization and in conducting original research in the area of algorithms. Since one of the goals of the proposal is the simplification of current results, the broad dissemination of the results of the research through conference and journal publication should increase understanding in the area. Potentially the results of the research will be part of a graduate class that the PI has taught on several occasions on the subject of approximation algorithms; notes from previous versions of the class are publically available and have been widely used. Finally, since many of the problems to be considered have practical importance, the improved bounds developed will affect the heuristics and exact optimization techniques used in practice.

组合优化中的许多问题都是 NP 难题，不太可能有有效的算法来找到最优解。其中包括工业实践中出现的众多问题，包括定位设施以满足客户需求、安排服务人员进行现场维修、调度车辆、构建具有特定连接属性的低成本网络、在芯片上布线等等。其他的。解决这些问题的典型方法是设计一些启发式方法，在实践中提供足够好的解决方案，或者，如果有足够的时间和资源并且最佳解决方案足够有价值，则设计一种穷举搜索算法来找到最佳解决方案。为了从数学上奠定启发式研究的基础，计算机科学家考虑了近似算法。这些是高效的多项式时间算法，可产生可证明在价值上接近最佳解决方案的解决方案。特别是，_ 近似算法生成的解的值在最优解值的 _ 因子之内。参数_有时被称为算法的性能保证。为了证明该算法产生接近最优的解决方案，必须使用最优值的界限。该界限通常是一个可以自行有效计算的量，并且在许多有趣的情况下基于问题的线性规划松弛。当多项式时间可计算界限（例如线性编程界限）用于证明强大的性能保证时，这对于使用穷举搜索解决最优问题的从业者也有影响，因为强界限对于快速修剪搜索很有用该提案的目标是研究当前近似算法知识状态中的一些异常现象，因为与其他科学领域一样，对异常现象的考虑能够最快地带来新的进展。几种已知的近似算法使用不可多项式时间计算的约束量；或者，即使多项式时间可计算，也很难先验地证明所考虑问题的界限。研究中包括的问题包括定位能够满足有限数量客户需求的设施（能力设施选址问题）、设计低成本网络（施泰纳树问题）以及车辆路线以最大限度地缩短平均时间。车辆到达客户处（最小延迟问题）。该研究的目标是表明这些算法可以用多项式时间可计算界限来重述，并且尽可能多地用涉及线性规划松弛的界限来重述。智力价值：可能需要重大的方法创新来解决这些问题。此外，PI 希望通过这项研究找到更简单、更好、更通用、更实用的近似算法。此外，如果可以找到其中一些问题的多项式时间可计算边界，则将导致更好的穷举搜索算法来寻找这些问题的最佳解决方案。 PI 是近似算法领域的领导者之一，在寻找新方法和改进算法方面拥有广泛的记录。更广泛的影响：PI 将培训研究生研究人员在更广泛的组合优化领域以及在算法领域。由于该提案的目标之一是简化当前结果，因此通过会议和期刊出版广泛传播研究结果应该会增加对该领域的理解。研究结果可能会成为 PI 多次讲授的关于近似算法主题的研究生课程的一部分；该课程先前版本的笔记已公开发布并已被广泛使用。最后，由于许多要考虑的问题具有实际重要性，因此改进的界限将影响实践中使用的启发式和精确优化技术。