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难的，不太可能有有效的算法来找到最优解。这些包括在工业实践中出现的许多问题，包括定位设施以满足客户需求，安排服务人员进行现场维修，调度车辆，构建具有特定连接属性的低成本网络，在芯片上布线等等。解决这些问题的典型方法是设计一些启发式算法，在实践中提供足够好的解决方案，或者，如果有足够的时间和资源，并且最优解足够有价值，则设计一个穷举搜索算法来找到最优解。这些都是有效的，多项式时间算法，产生的解决方案是可证明的价值接近最优解。特别地，_近似算法产生其值在最优解的值的_因子内的解。参数_有时被称为算法的性能保证。为了证明该算法产生一个接近最优的解决方案，必须使用最优值的界限。这个界限通常是一个可以自己有效计算的量，并且在许多有趣的情况下是基于问题的线性规划松弛。当一个多项式时间的可计算的界限，如线性规划界限，被用来证明一个强的性能保证，这也有影响的从业者解决问题的最优使用穷举搜索，因为一个强的界限是有用的快速修剪搜索空间。该提案的目标是研究一些异常的近似算法的知识现状，因为在其他领域的科学，对反常现象的考虑最快地导致新的进展。几个已知的近似算法使用的约束量不是多项式时间可计算的;或者，即使多项式时间可计算，也很难显示被考虑问题的先验边界。包括在研究中的问题定位设施，可以服务于有限数量的客户需求（capacitated设施定位问题），设计低成本的网络（施泰纳树问题），和车辆的路由，以尽量减少车辆到达客户的平均时间（minimumlatency问题）。研究的目标是表明，这些算法可以重述多项式时间可计算的界限，并尽可能经常，涉及线性规划relaxations.Intellectual优点的界限：显着的方法创新将可能需要resolvethese issues。此外，PI希望通过这项研究找到更简单，更好，更通用，更实用的近似算法。此外，如果多项式时间可计算的界限，可以找到这些问题中的一些，它将导致更好的穷举搜索算法，找到这些问题的最佳解决方案。PI是近似算法领域的领导者之一，在发现新方法和改进算法方面有着广泛的记录。更广泛的影响：PI将在更广泛的组合优化领域培养研究生研究人员，并在算法领域进行原创性研究。由于该提案的目标之一是简化目前的结果，通过会议和期刊出版物广泛传播研究结果应增加对该领域的了解。潜在的研究结果将是一个研究生班的一部分，PI已经教过几次近似算法的主题;从以前版本的类的笔记是免费提供的，并已被广泛使用。最后，由于要考虑的许多问题具有实际重要性，改进的边界开发将影响在实践中使用的算法和精确的优化技术。