Faster core-set constructions and data-stream algorithms in fixed dimensions (Q2507158)

The author investigates \((1+\epsilon)\)-factor approximation algorithms. In the first section an overview of existing methods is presented as well as a series of useful background definitions. The next section presents the main contribution of this work which results in improved performance. A series of theorems are proven and two possible approaches are considered, for both of which the computations are speeded up. The second part of the article considers algorithms under the data-stream model. Improved results are also obtained for this case, both for the general case as well as for two dimensional case, where a refinement is on the technique is also presented. The paper concludes with a list of useful references.