Design and Analysis of Algorithms for Coping with NP-Hardness

应对NP难题的算法设计与分析

• 批准号: 9713482
• 负责人: Dorit Hochbaum
• 金额: $ 25.73万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-09-15 至 2001-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9713482&HistoricalAwards=false
• 关键词: Design; Analysis; Algorithms; Coping; NP

9713482 Hochbaum This project will study three approaches to devising algorithms and analyzing their effectiveness for obtaining solutions to hard optimization problems. These three approaches (1) probabilistic analysis of heuristic algorithms, (2) worst case analysis of heuristic algorithms, and (3) implicit enumerative algorithm design are often pursued separately, since the techniques involved are usually quite different. Considerable insight can be gained by employing all three approaches in parallel. Algorithm design is largely an ad hoc procedure, whether the goal is to devise an algorithm with good performance based on its average or worst case performance, or to provide bounding procedures within a branch-and-bound context. This research will focus on devising unified techniques applicable to large problem classes. The research is expected to generate, among other outcomes, a unified technique based on the choice of problem formulation and the application of specific types of transformation on the formulations that make obtaining good feasible solutions easy, at a limited loss of optimality. This technique has enormous potential for deriving approximation algorithms with good performance and generating tight bounds that are useful for enumerative algorithms. The technique is also a unified approach applicable to a wide range of problems. If the investigation using all three approaches is successful, it will provide new and useful methods for improving the quality of solutions for problems in areas varying from telecommunications and scheduling to locations, clustering and circuit testing.

小行星9713482 本计画将研究三种方法来设计演算法，并分析其有效性，以获得困难最佳化问题的解决方案。 这三种方法（1）启发式算法的概率分析，（2）启发式算法的最坏情况分析，和（3）隐式枚举算法设计通常是分开进行的，因为所涉及的技术通常是完全不同的。 同时采用这三种方法可以获得相当多的见解。 算法设计在很大程度上是一个特设的过程，无论目标是设计一个算法，具有良好的性能的基础上，其平均或最坏的情况下的性能，或提供一个分支和边界的上下文中的边界程序。 这项研究将集中在设计适用于大型问题类的统一技术。 这项研究预计将产生，除其他成果外，一个统一的技术的基础上选择的问题制定和特定类型的转换的配方，使获得良好的可行的解决方案容易，在有限的损失的最优性的应用。 这种技术具有巨大的潜力，推导出具有良好性能的近似算法，并产生紧密的边界，是有用的枚举算法。 该技术也是一个统一的方法，适用于广泛的问题。 如果使用所有三种方法的调查是成功的，它将提供新的和有用的方法，以提高质量的解决方案，在不同的领域，从电信和调度的位置，集群和电路测试。