Design and Analysis of Algorithms for Coping with NP-Hardness

这笔拨款是为了研究设计算法的三种方法，并分析它们对获得困难优化问题的解的有效性。这三种方法：(1)启发式算法的概率分析；(2)启发式算法的最坏情况分析；(3)(隐式)枚举算法设计-通常是分开进行的，因为涉及的技术通常非常不同。前两种方法通常被认为是理论上的，但它们可能具有深远的实践意义。有人提出，通过同时使用这三种方法，可以获得相当大的洞察力。算法设计在很大程度上是一个特别的过程，无论目标是基于其平均或最差情况的性能来设计具有良好性能的算法，还是在分支定界的上下文中提供定界过程。这项资助是为了设计适用于某些问题类的统一技术，并扩大所开发的统一技术的应用范围。除了其他主题外，研究是为了解决一种特定的技术，称为因子2变换。这一技术在推导适用于广泛问题的枚举算法的恒定因子近似和紧界方面具有巨大的潜力。此外，该技术导致所谓的“持久性”结果，其允许在枚举过程内固定某些变量，从而限制搜索空间。这一技术已经被证明在不同的领域有着广泛的应用，从调度问题，到布局问题，到几何规划和布局问题，到选址问题，以及推广的可满足性问题。

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.