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-硬化，并且不太可能具有有效的算法来找到最佳解决方案。其中包括在行业中实践中出现的多种问题，包括为服务客户需求找到设施，安排服务人员进行现场维修，派遣车辆，构建具有特定连接性能的低成本网络，筹码上的路由电线以及许多其他。解决这些问题的典型方法是设计一些启发式方法，在实践中提供了足够好的解决方案，或者，如果有足够的时间和资源可用并且最佳解决方案足够有价值，则可以设计详尽的搜索算法来找到最佳的解决方案。在数学上，计算机科学家在数学上依据，计算机科学家考虑了近似学院的近似学院。这些是有效的多项式时间算法，可产生与最佳解决方案相关的溶液。特别是，_- approximation算法会产生一个解决方案，其值在最佳解决方案值的一个; _; e;的值之内。参数_有时称为算法的性能保证。为了证明该算法产生近乎最佳的解决方案，必须使用最佳值的结合。该界限通常是可以自行进行有效计算的数量，在许多有趣的情况下，基于问题的线性编程放松。当使用多项式计算界限（例如线性编程绑定）被用来证明具有强大的性能保证时，这也对使用详尽搜索解决最佳性问题的从业人员具有影响，因为强有力的范围可用于快速修剪搜索空间。该提案的目的是在当前的其他领域中，在其他领域中，在其他方面进行了近似阶段的考虑，而其他科学则是与科学的相关事物的考虑，因为该领域是科学的，因为该领域是与科学的相关性。进步。几种已知的近似算法用作不可计算的多项式时间的界数；或者，即使多项式时间可计算，也很难显示出在考虑的问题上的界限。研究中包括的问题是找到可以满足客户需求数量的设施（电容设施位置问题），设计低成本网络（Steiner树问题）以及车辆路由以最大程度地减少车辆到达客户到达客户的平均时间（最小值问题）。该研究的目的是证明这些算法可以根据多项式时间可计算界限来重述，并且尽可能多地涉及线性编程放松的范围。智能优点：解决vethese问题可能需要重大的方法论创新。此外，由于这项研究，PI希望找到更简单，更好，更一般和更实用的近似算法。此外，如果在其中一些问题中找到多项式时间可计算界限，则将导致更好的详尽搜索算法来找到这些问题的最佳解决方案。 PI是近似算法领域的领导者之一，并且具有寻找新方法和改进算法的广泛记录。Broader的影响：PI将培训组合式优化领域的研究生研究人员，并在算法领域进行原始研究。由于该提案的目标之一是简化当前结果，因此通过会议和期刊出版物对研究结果的广泛传播应提高该领域的理解。研究结果可能是PI在近似算法上多次教授的研究生类别的一部分。班级以前版本的注释已公开可用，并且已被广泛使用。最后，由于许多要考虑的问题具有实际重要性，因此所开发的改进界限将影响实践中使用的启发式和精确优化技术。