Topics in Parametric Optimization



Parametric problems are those whose input depends continuously on one or more values. This award supports work in two fundamental areas in parametric optimization. The first is fixed-dimensional optimization, with special emphasis on problems whose objective function can be efficiently evaluated at any point by a well-behaved algorithm. Problems of this sort arise, for example, in Lagrangian relaxation. The main question is to determine the conditions under which evaluation is as easy as global optimization, within the context of Megiddo's method of parametric search. The second area to be investigated is the construction of parameter space decompositions yielding optimal solutions for all parameter values. One issue is obtaining bounds on the number of regions of the decomposition. This will be studied in part within a framework that captures the essence of problems as diverse as stable marriage and evolutionary tree construction. Another question is whether one can accelerate the construction of the decomposition by exploiting structural similarities between adjacent regions.

2000-07-01 to 2005-06-30
Award Amount: 
Award Number: