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 spacess 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.

Definition

be a finite set to their nearest center.

,

is a user-defined approximation parameter.

so that

to the cost.

Some literature distinguishes between:

• Strong coresets.

• Weak coresets: The guarantee holds only for solutions near the optimum.

Construction techniques

Coresets are typically constructed using one or more of the following techniques:

• Importance sampling: Points are sampled with probability proportional to their sensitivity (their maximum relative influence on the objective function).

• Random sampling and ε-approximations: Techniques from VC theory are used to guarantee uniform convergence.

• Geometric partitioning: Space is partitioned and representative points are selected from each region.

• Merge-and-reduce frameworks: Used in streaming and distributed settings to maintain coresets over time.

.

Applications

Clustering

Coresets are widely used in clustering problems such as k-means clustering, k-median, and metric k-center.-approximation for the original dataset.

This enables scalable clustering in large datasets and forms the basis of several practical machine learning systems.

Geometric optimization

Coresets have been developed for problems including:

• Minimum enclosing ball

• Facility location

• Projective clustering

• Shape fitting

In low-dimensional settings, coresets often yield polynomial-time approximation schemes.

Regression and machine learning

In regression problems such as least-squares fitting, coresets provide smaller weighted datasets that preserve the objective value. They are also used in:

• Support vector machines

• Subspace approximation

• Hyperparameter optimization

More recently, coresets have been explored for dataset summarization and acceleration of training in large-scale machine learning pipelines.

Streaming and distributed computation

In streaming models, data points arrive sequentially and storage is limited. Merge-and-reduce techniques maintain a small coreset whose size depends only on ε and problem parameters. Similarly, in distributed systems, composable coresets allow each machine to compute a local coreset, which can then be combined centrally while preserving approximation guarantees.

Related concepts

Coresets are related to:

• ε-approximations and ε-nets in range spaces

• Randomized sketching techniques

• Dimensionality reduction

• Sublinear and streaming algorithms

References