Algorithms in Parametric Optimization

讨论了组合算法设计中的两个主题：(1)具有顶点和/或边权的图的参数问题，特别是Megiddo的参数搜索方法；(2)物种集的进化树的构建，重点是根据物种所展示的特征来描述物种的方法。首先，参数计算处理输入是一个或多个参数的连续函数的问题；它在以下方面有应用：(1a)灵敏度分析(即研究成本的变化如何影响问题的最佳解决方案的选择)；(1b)拉格朗日松弛(一种处理优化问题中困难约束的强大启发式)；(1c)计算几何；(1D)计算生物学。这个项目的主要目标是研究在什么情况下参数问题可以在与其基本的非参数问题相同的时间范围内得到解决。这导致了对并行性、动态算法以及图形和空间分解技术在参数搜索中的作用的研究。第二个目标是获得某些参数问题的最优解随着参数在其范围内变化而变化的次数的界限。其次，进化树或进化史描述了一组物种是如何从共同的祖先进化而来的。系统发育构建的研究主要涉及(2a)为重要的特殊情况寻找更快的算法，以及(2b)开发更新现有树的动态算法。动态算法在实践中特别有用，因为它们允许科学家分析不同的进化场景，并修改现有的树，以反映关于物种集合的更多知识。看来，开发高效的动态算法需要对承认某些种类的系统发育的物种集合进行清晰的描述。这样的特征本身可能是有意义的。

Two topics in the design of combinatorial algorithms are addressed: (1) Parametric problems on graphs with vertex and/or edge weights, with particular emphasis on Megiddo's method of parametric search; (2) The construction of evolutionary trees for sets of species, focusing on methods where species are described by the characteristics they exhibit. First, parametric computing deals with problems where the input is a continuous function of one or more parameters; it has applications in: (1a) Sensitivity analysis (that is, studying how changes in costs affect the choice of optimum solution to a problem); (1b) Lagrangian relaxation (a powerful heuristic for coping with difficult constraints in optimization problems); (1c) computational geometry; and (1d) computational biology. The primary goal of this project is to study the circumstances under which parametric problems can be solved within the same time bound as their underlying non-parametric problems. This leads to an examination of the roles of parallelism, dynamic algorithms, and graph and space decomposition techniques in parametric search. A secondary goal is to obtain bounds on the number of times the optimum solution to certain parametric problems changes as the parameter is varied across its range. Second, an evolutionary tree or phylogeny describes how a set of species evolved from a common ancestor. The research on phylogeny construction deals primarily (2a) with finding faster algorithms for important special cases, and (2b) with developing dynamic algorithms for updating existing trees. Dynamic algorithms are particularly useful in practice, as they permit scientists to analyze different scenarios for evolution and to modify existing trees to reflect increased knowledge about sets of species. It appears that the development of efficient dynamic algorithms requires clean characterizations of sets of species admitting certain kinds of phylogenies. Such characterizations may be of interest in their own right.