Modified algorithms for the minimum volume enclosing axis-aligned ellipsoid problem

作者：Cong, Wei-jie^*; Liu, Hong-wei

来源：Discrete Applied Mathematics, 2010, 158(6): 627-635.

DOI：10.1016/j.dam.2009.12.003

• Minimum volume ellipsoids
• Axis-aligned ellipsoids
• Core sets
• Approximation algorithms
• Complexity analysis

Consider the problem of computing a (1 + epsilon)-approximation to the minimum volume axis-aligned ellipsoid (MVAE) enclosing a set of m points in R(n). We first provide an extension and improvement to algorithm proposed in Kumar and Yildirim (2008)[5] (the KY algorithm) for the MVAE problem. The main challenge of the MVAE problem is that there is no closed form solution in the line search step (beta). Therefore, the KY algorithm proposed a certain choice of beta that leads to their complexity and core set results in solving the MVAE problem. We further analyze the line search step to derive a new beta, relying on an analysis of up to the fourth order derivative. This choice of beta leads to the improved complexity and core set results. The second modification is given by incorporating "away steps" into the first one at each iteration, which obtains the same complexity and core set results as the first one. In addition, since the second modification uses the idea of "dropping points", it has the potential to compute smaller core sets in practice. Some numerical results are given to show the efficiency of the modified algorithms.

• 出版日期2010-3-28
• 单位西安电子科技大学