"Design, analysis and theory of algorithms"

算法设计和分析在正在开发的算法的复杂性以及最近的算法已成为必不可少的不断扩大的应用领域方面取得了重大进展。然而，算法设计仍然主要是一门艺术。这个研究项目的目标是使算法设计更像是一门科学，而不是一门艺术。也就是说，我们希望帮助开发一种算法理论，使我们能够更好地理解应用于各种问题领域的一般算法方法的好处和局限性。诚然，这个总体项目既过于含糊，也过于雄心勃勃。因此，在更实用的术语中，我正在研究众所周知的“概念上简单的元算法”的能力和局限性，例如贪婪算法、动态规划、原始的对偶/局部比算法和局部搜索算法。为了做到这一点，我们提出了精确的模型，这些模型捕捉了与各种问题领域相关的此类算法的特定实例。我们继续设计和分析特定框架内的算法，并建立关于模型的不可能结果(例如，不逼近界)。这种方法与人们试图建立的关于VIS复杂性界限的基本限制形成对比(例如，在多项式时间或对数空间中什么可以计算，什么不可以计算)。相反，我们试图建立独立于复杂性问题的限制，而不是基于算法的受限设计来建立这样的限制。特别地，我们证明了无论P=NP是否成立的结果。

Algorithm design and analysis has seen significant progress in the sophistication of the algorithms being developed as well as in the expanding set of application areas where recent algorithms have become essential. However, algorithm design still remains mainly an art. The goal of this research project is to make algorithm design somewhat more of a science than an art. Namely, we wish to help develop a theory of algorithms that would allow us to better understand the benefits and limitations of general algorithmic approaches as applied to various problem domains. This general project is admittedly both too vague and too ambitious. So in more pragmatic terms, I am studying the power and limitations of well known "conceptually simple meta algorithms" such as greedy algorithms, dynamic programming, primal dual/local ratio algorithms and local search algorithms. To do so, we propose precise models that capture particular instances of such algorithms in relation to a wide variety of problem domains. We proceed to both design and analyze algorithms within a particular framework and as well to establish impossibility results (e.g. inapproximination bounds) with respect to the model. This approach stands in contrast to the fundamental limitations one tries to establish vis a vis complexity bounds (e.g. what can and cannot be computed in polynomial time or logarithmic space). Rather we try to establish limitations independent of complexity issues but instead establish such limitations based on the restricted design of the algorithm. In particular, we prove results that hold whether or not P = NP.