Design and Analysis of Algorithms for Coping with NP-Hardness

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

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

The grant is to study three approaches for 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 algorithm; and (3) (implicit) enumerative algorithm design-are often pursued separately, since the techniques involved are usually quite different. The first two approaches are often considered theoretical in nature, yet they can have profound practical implications. It is proposed that 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. The grant is to devise unified techniques applicable to certain problem classes and expand the range of applications of the developed unified techniques.The research is to address, among other topics, a specific technique, which called factor-2-transformations. This technique has enormous potential for deriving constant factor approximations and tight bounds that are useful for enumerative algorithms applicable to a wide range of problems. In addition, the technique leads to so-called "persistency" results that permit the fixing of some variables within an enumerative procedure and thus limiting the search space. This technique has already been shown to have a wide range of applications in diverse areas ranging from scheduling, to layout problems, to geometric planning and packing problems, to location problems and to generalize satisfiability problems.

这项拨款是研究三种方法，设计算法和分析其有效性，以获得解决困难的优化问题。 这三种方法：（1）启发式算法的概率分析;（2）启发式算法的最坏情况分析;和（3）（隐式）枚举算法设计--通常是分开进行的，因为所涉及的技术通常是完全不同的。前两种方法通常被认为是理论性的，但它们可能具有深远的实际影响。 有人建议，相当大的洞察力，可以通过采用所有三种方法并行。 算法设计在很大程度上是一个特设的过程，无论目标是设计一个算法，具有良好的性能的基础上，其平均或最坏的情况下的性能，或提供一个分支和边界的上下文中的边界程序。该基金旨在设计适用于某些问题类别的统一技术，并扩大已开发的统一技术的应用范围。该研究旨在解决其他主题中的一个特定技术，称为因子2变换。 这种技术具有巨大的潜力，推导出常数因子近似和严格的界限，适用于广泛的问题的枚举算法是有用的。 此外，该技术导致了所谓的“持久化”结果，允许在枚举过程中固定某些变量，从而限制了搜索空间。 这种技术已经被证明有广泛的应用在不同的领域，从调度，布局问题，几何规划和包装问题，位置问题和广义可满足性问题。