Algorithms in Parametric Optimization

参数最优化处理目标函数是一个或多个独立参数的函数的问题。这类问题出现在各种环境中，包括动态计算几何结构和将模块分配给分布式系统中的处理器的问题(其中在给定处理器上执行作业所需的时间量可能取决于处理器的负载)。参数问题的极小化图是将参数空间划分为多个区域，每个区域是某一特定解最优解的最大参数值集合。利用点定位技术，可以从极小化图中有效地得到给定参数值的最优解。本课题主要研究了以下几个方面：1.求出了特定问题极小化图的几何复杂性的界。这些界限允许人们估计在其中定位一个点所需的时间量。2.设计有效的通用策略和特定问题策略来构建最小化图。

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.