Coreset

Coreset implements algorithms for discrete diversity, dispersion, and coverage subset selection: choosing a representative subsample of points under one of several objectives.

Solvers

Solvers support precomputed distance matrices (dist objects), matrices of Euclidian coordinates, or lists of elements from which distances can be calculated. Each solver is accompanied by a function that evaluates its objective against an arbitrary selection of elements.

MMDP (max-min dispersion)

The Max-Min Diversity Problem (MMDP, the discrete p-dispersion objective) selects $k$ elements such that the minimum distance between any pair of selected elements is as large as possible; the chosen elements are maximally separated.

Function	Method	Use
DropAdd()	DropAdd tabu search	~99%-optimal heuristic
Grasp()	GRASP with path-relinking metaheuristic	Slower but powerful heuristic
ExactMaxMin()	Node-packing integer program	Proven optimum, small $k$

Max-sum dispersion (maximum diversity)

The Max-Sum dispersion problem selects $k$ elements such that the summed distance between all pairs of selected elements is as large as possible.

Function	Method	Use
ExactMaxSum()	Per-node MILP linearisation, floored by multi-start local search	Proven optimum for total pairwise distance, small $k$ (needs highs)

Max-mean dispersion

The analogous Max-Mean dispersion problem chooses a number of elements so as to maximize the mean distance between selected pairs.

Function	Method	Use
MaxMean()	Reinforcement-learning tabu search	Maximize mean pairwise distance; subset size free; signed distances supported

k-centre (min-max covering)

The discrete k-centre problem selects $k$ elements such that the maximum distance from any element in the original set to a selected element is as small as possible.

Function	Method	Use
KCentre()	Critical Dominating Set heuristic	~1–3.5% of optimum at $O(N^2 \log N)$, typically far tighter than FarFirst()
ExactKCentre()	Exhaustive covering search	Proven optimum, small $k$

Maximum-entropy (maxdet) selection

The maximum entropy problem selects the $k$ elements that contain the highest amount of information about the original set: a minimally redundant pick.

Function	Method	Use
MaxEntropy()	Greedy pivoted-Cholesky selection, with exact enumeration for small instances	Maximize the log-determinant (spanned volume) of a similarity kernel; density-blind

Installation

Install from CRAN with:

install.packages("Coreset")

Install the development version from GitHub:

if (!require("pak")) install.packages("pak")
# pak::pkg_install("ms609/Coreset")
install.packages("Coreset", repos = c('https://ms609.r-universe.dev', 'https://cloud.r-project.org'))

Related problems

Coreset selects a subset from a given set of elements. Several established packages solve neighbouring objectives:

• k-medoids / k-median selects elements that minimize the mean distance from each element to its nearest centre. Implementations include:

  • cluster::pam(): generates the full O(N²) dissimilarity matrix, and hence caps at n ≤ 65 536;
  • banditpam, a matrix-free $O(N \log N)$ implementation restricted to coordinate data;
  • cluster::clara() (PAM / FastPAM / FasterPAM);
  • ClusterR::Cluster_Medoids().

• k-means (stats::kmeans()) selects elements so as to minimize the within-cluster sum of squares around centres that are coordinate means, not data points; as such, it applies only to Euclidean coordinates. k-means++ (TreeDist::KMeansPP()) initializes its selection using D²-weighted seeding, a randomized relative of FarFirst()'s farthest-first traversal.

• maximin solves the related design problem of adding new points at positions that maximize the minimum inter-point distance.