Parametric optimization deals with problems where the objective function is a function of one or more independent parameters. Such questions arise in a variety of settings, including dynamic computational geometry and the problem of allocating modules to processors in a distributed system (where the amount of time needed to execute a job on a given processor may depend on the load of the processor). The minimization diagram of a parameter problem is a partition of the parameter space into regions, where each is the maximal set of parameter values for which a particular solution is optimum. The optimum solution for given parameter values can be efficiently obtained from the minimization diagram using point location techniques. This project investigates the following: 1. Obtaining bounds on the geometric complexity of the minimization diagram for particular problems. These bounds allow one to estimate the amount of time needed to locate a point within it. 2. Devising efficient general-purpose and problem-specific strategies for constructing the minimization diagram.
