Coreset

In computational geometry and approximation algorithms, a coreset is a small, possibly weighted subset of an input point set that approximately preserves the value of a specified optimization problem. Solving the problem on the coreset yields a solution whose cost is provably close to the optimal solution for the full dataset. Coresets are widely used in geometric optimization, cluster analysis, data streams, and large-scale machine learning to reduce computational complexity while maintaining theoretical guarantees. Many geometric optimization problems admit coresets of size bounded by a function of the approximation parameter ε and the dimension, but independent of the input size. When such a coreset can be constructed in linear or near-linear time, it yields a polynomial-time approximation scheme (PTAS) or efficient approximation algorithm. The concept of coresets emerged in the late 1990s and early 2000s within computational geometry, as part of a broader effort to develop approximation schemes for high-dimensional geometric problems. Early work connected coresets to ε-approximations and ε-nets in range spaces and VC dimension theory. Subsequent research extended the framework to clustering, streaming models, and distributed computation.…

In computational geometry and approximation algorithms, a coreset is a small, possibly weighted subset of an input point set that approximately preserves the value of a specified optimization problem. Solving the problem on the coreset yields a solution whose cost is provably close to the optimal solution for the full dataset. Coresets are widely used in geometric optimization, cluster analysis, data streams, and large-scale machine learning to reduce computational complexity while maintaining theoretical guarantees. Many geometric optimization problems admit coresets of size bounded by a function of the approximation parameter ε and the dimension, but independent of the input size. When such a coreset can be constructed in linear or near-linear time, it yields a polynomial-time approximation scheme (PTAS) or efficient approximation algorithm. The concept of coresets emerged in the late 1990s and early 2000s within computational geometry, as part of a broader effort to develop approximation schemes for high-dimensional geometric problems. Early work connected coresets to ε-approximations and ε-nets in range spaces and VC dimension theory. Subsequent research extended the framework to clustering, streaming models, and distributed computation. Over time, coresets became a central tool in large-scale data analysis, particularly for clustering and regression problems, where exact computation on massive datasets is computationally infeasible. f(S, x) = \sum_{p \in S} w(p)\, c(p, x), where c(p, x) is the contribution of point p to the cost. Some literature distinguishes between: Strong coresets: The approximation guarantee holds uniformly for all candidate solutions x . Weak coresets: The guarantee holds only for solutions near the optimum.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373892938 under CC BY-SA 4.0; modifications have been made.