Minimax parametric optimization problems and multi-dimensional parametric searching
Minimax parametric optimization problems and multi-dimensional parametric searching
复制标题
DOI：
10.1145/380752.380777
复制
发表时间：
2001-07
期刊：
影响因子：
--
通讯作者：
T. Tokuyama
中科院分区：
文献类型：
--
作者：
T. Tokuyama
参数极大极小问题是灵敏度分析中的一个基本问题，它求出的参数值使组合极大化问题的解的权重最小。此外，计算几何中的一些问题可以表述为参数极大极小问题。当原非参数问题有一个有效的并行算法时，参数搜索范式给出了一个求解单参数凸参数Minimax问题的有效序列算法。我们考虑对于常数d具有d个参数的参数极大极小问题，并使用多维版本的参数搜索范式来解决它。作为一个新的特征，我们在参数空间中给出了一个可行域，参数向量必须位于该可行域中。作为应用获得的典型结果有：（1）某些几何问题的有效解，包括凸多面体之间d维空间中最小直径桥接问题的理论有效解。(2)以参数多项式拟阵优化为例，计算参数向量最小化d维k-最大线性参数元的时间复杂度为O（n log n）。
The parametric minimax problem, which finds the parameter value minimizing the weight of a solution of a combinatorial maximization problem, is a fundamental problem in sensitivity analysis. Moreover, several problems in computational geometry can be formulated as parametric minimax problems. The parametric search paradigm gives an efficient sequential algorithm for a convex parametric minimax problem with one parameter if the original non-parametric problem has an efficient parallel algorithm. We consider the parametric minimax problem with d parameters for a constant d, and solve it by using multidimensional version of the parametric search paradigm. As a new feature, we give a feasible region in the parameter space in which the parameter vector must be located. Typical results obtained as applications are: (1) Efficient solutions for some geometric problems, including theoretically efficient solutions for the minimum diameter bridging problem in d-dimensional space between convex polytopes. (2) Parametric polymatroid optimization, for example, O(n log n) time algorithm to compute the parameter vector minimizing k-largest linear parametric elements with d dimensions.