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.