Name
Abstract | ||
|---|---|---|
Consider the problem of computing a (1+@e)-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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.dam.2009.12.003 | Discrete Applied Mathematics |
Keywords | Field | DocType |
closed form solution,approximation algorithms,line search | Approximation algorithm,Discrete mathematics,Combinatorics,Ellipsoid,Fourth order,Closed-form expression,Algorithm,Line search,Mathematics | Journal |
Volume | Issue | ISSN |
158 | 6 | 0166-218X |
Citations | PageRank | References |
1 | 0.36 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wei-Jie Cong | 1 | 14 | 2.40 |
| Hongwei Liu | 2 | 78 | 12.29 |