Discrete Diversity, Dispersion, and Coverage Subset Selection
Overview
Solves discrete location objectives on a distance matrix or Euclidean coordinate set. The Max-Min Diversity (MMDP / p-dispersion) objective, which maximizes the minimum pairwise distance within a selection of k items, is solved by farthest-first selection (Gonzalez 1985) doi:10.1016/0304-3975(85)90224-5; the DropAdd tabu-search heuristic (Porumbel, Hao & Glover 2011) doi:10.1007/s10479-011-0898-z, GRASP with path-relinking (Resende, Marti, Gallego & Duarte 2010) doi:10.1016/j.cor.2008.05.011, and an exact node-packing integer program (Sayyady & Fathi 2016) doi:10.1016/j.ejor.2016.02.026. The Max-Mean Dispersion objective, which selects a subset of unrestricted size maximising the sum of its pairwise distances divided by the number of selected elements, is solved by reinforcement-learning-guided tabu search (Nijimbere et al. 2020) doi:10.3934/jimo.2020115. The discrete k-centre (min-max covering / facility location) objective, which chooses k centres to minimise the largest distance from any point to its nearest centre, is solved via the CDSh heuristic (Garcia-Diaz et al. 2017 doi:10.1007/s10732-017-9345-x, 2019 doi:10.1109/ACCESS.2019.2933875), and an exact minimum-cover integer program. The maximum-entropy (maxdet) objective, which maximises the log-determinant of a similarity kernel built from the distances (Shewry & Wynn 1987 doi:10.1080/02664768700000020; the mode of a determinantal point process, Kulesza & Taskar 2012 doi:10.1561/2200000044), is solved by greedy pivoted-Cholesky selection and, for small instances, exact enumeration.
Coreset selects a representative subset of a fixed candidate set under an
arbitrary distance, solving four discrete location objectives on a distance
matrix, a coordinate matrix, or an on-demand distance-column oracle.
Max-Min diversity (MMDP / discrete _p_-dispersion)
Maximises the minimum pairwise distance within a subset of size k.
FarFirst(): greedy farthest-first selection (Gonzalez 1985), with a choice of peripheral seeding strategies, distinct-seed random restarts (nSeeds), and a robust ensemble default.DropAdd(): DropAdd tabu search (Porumbel et al. 2011), which can compute distances between pairs on the fly rather than needing a complete matrix _a priori_.Grasp(): GRASP with path relinking (Resende et al. 2010), attaining the highestT_kof the package's heuristics on small to medium instances.
Show all changes in 1.0.0Hide the rest of the changes in 1.0.0
ExactMaxMin(): exact node-packing optimum (Sayyady & Fathi 2016), decided by clique search.
Max-Mean dispersion
MaxMean(): reinforcement-learning-guided tabu search (Nijimbere et al. 2020), selecting a subset of unrestricted size that maximises the mean pairwise distance.
Discrete _k_-centre
Minimises the largest distance from any element to its nearest selected centre.
KCentre(): the CDSh covering heuristic (Garcia-Diaz et al. 2017, 2019).ExactKCentre(): exact minimum-cover optimum.
Max-Sum diversity and maximum entropy
ExactMaxSum(): exact solver for the Max-Sum Diversity Problem (requires 'highs').MaxEntropy(): maximum-entropy (maxdet) selection — the mode of a determinantal point process — by greedy pivoted-Cholesky selection, and by exact enumeration for small instances.
Scoring and utilities
MinDist(),MeanDist()andKCentreRadius()score an arbitrary selection under the max-min, max-mean and _k_-centre objectives respectively.PickPoint()exposes the peripheral seed indices directly.DropAdd()andGrasp()accept amaxCandidatescomposable-coreset cap, thinning the candidate set withFarFirst()before the expensive search and mapping the chosen indices back to the original numbering.- Each solver returns a classed object with
print(),format()and (where informative)summary()methods giving a terse or detailed report of the selection, the achieved objective, and the search effort. - Solver behaviour is tunable through
options(Coreset.symmetryTolerance = ), which sets how large a rounding discrepancy betweend[i, j]andd[j, i]is repaired rather than refused, andoptions(Coreset.progress = ).
From NEWS.md in the release
Install
Health
- OK13 OKNow
- OK5 OK2026-09-18
Documentation
- Help pages
- 64 (45 internal)includes a package overview page
- Examples that run
- 100%19 run in a plain check
- Exported functions with examples
- 100%
- Documented parameters
- 95%
- Return-value docs
- 100%
- Help pages citing references
- 16% with a bibliography file
Downloads
Repository
- PRs merged (all time)
- 94%
- Median days to close, 50 most recently updated closed issues
- 20
- Median days to close, 50 most recently updated closed PRs
- 0
Stars over time
Issues over time
PRs over time
Commits over time
12 development-tooling and community-health practices detected across 8 families in the upstream repository
Checks run against github.com/ms609/coreset on 2026-10-18.
The R CMD check workflow runs on Linux, macOS and Windows, and on R-devel
Show all practicesHide 4 practices
This repository shows signs of AI coding tools.
- Claude Codefirst seen on or before 2026-06-05Seen in the repository: .claudeNamed in .Rbuildignore: .claudePull request it wrote: opened by a project memberCommits: at least 156 crediting it in the message
- Claude Opus 536 commits · Jul to Aug 2026
- Claude Fable 532 commits · Aug 2026
- Claude Opus 4.824 commits · Jun to Aug 2026
- Claude Sonnet 4.64 commits · Jun 2026
- Claude Sonnet 53 commits · Aug 2026
1 more model not listed. Some of these counts are a minimum, because the search stopped before the oldest commits.
Dependencies
Code & Tests
People & History
- 1.0.0Latest2026-09-17 · current release
- RR 4.6.0 released · 2026-04-24
Package metadata
- First published
- 2026-09-17
- Total releases
- 1 / 1 yrs
- License
- GPL (>= 3) OSI
- Minimum R
- ≥ 4.1
- Download size
- 331 KB
Cite
Cite this package
Run in R for the authors' preferred citation:
citation("Coreset")The package provides a citation file that builds its entry when R runs it. Run citation() to see it.
Cite the R Observatory
For a number measured here: a download total, a coverage figure, an archival date.
From data release v2026-10-21, which the citation names so these numbers can be found later. More on citing and the projects behind them.