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.