Abstract:
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.
Funding Organization
Algorithms in Parametric Optimization
Award Amount
$163,965
Award Number
9520946