Design and Analysis of Algorithms for Coping with NP-Hardness

9713482 Hochbaum这个项目将研究三种方法来设计算法，并分析它们的有效性，以获得硬优化问题的解。这三种方法(1)启发式算法的概率分析，(2)启发式算法的最坏情况分析，以及(3)隐式枚举算法设计通常是分开进行的，因为涉及的技术通常是完全不同的。通过并行使用这三种方法，可以获得相当大的洞察力。算法设计在很大程度上是一个特别的过程，无论目标是基于其平均或最差情况性能设计具有良好性能的算法，还是在分支和绑定上下文中提供边界过程。本研究将集中于设计适用于大型问题类的统一技术。该研究预计将产生一种统一的技术，该技术基于问题形式的选择和对公式的特定类型转换的应用，这些转换使得在有限的最优性损失下容易获得良好的可行解决方案。这种技术在导出性能良好的近似算法和生成对枚举算法有用的紧边界方面具有巨大的潜力。该技术也是一种适用于广泛问题的统一方法。如果使用这三种方法的调查是成功的，它将提供新的和有用的方法，以提高从电信和调度到地点、集群和电路测试等领域的问题的解决方案的质量。

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.