Coreset: Discrete Diversity, Dispersion, and Coverage Subset Selection
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.
| Version: |
1.0.0 |
| Depends: |
R (≥ 4.1) |
| Imports: |
cli (≥ 3.0.0), Rcpp, Rdpack (≥ 0.7), stats |
| LinkingTo: |
Rcpp |
| Suggests: |
highs, knitr, Matrix, quarto, rprojroot, spelling, testthat (≥ 3.0.0) |
| Published: |
2026-09-17 |
| DOI: |
10.32614/CRAN.package.Coreset (may not be active yet) |
| Author: |
Martin R. Smith 
[aut, cre, cph] |
| Maintainer: |
Martin R. Smith <martin.smith at durham.ac.uk> |
| BugReports: |
https://github.com/ms609/Coreset/issues |
| License: |
GPL (≥ 3) |
| URL: |
https://ms609.github.io/Coreset/ |
| NeedsCompilation: |
yes |
| Language: |
en-GB |
| Citation: |
Coreset citation info |
| Materials: |
NEWS |
| CRAN checks: |
Coreset results |
Documentation:
Downloads:
Linking:
Please use the canonical form
https://CRAN.R-project.org/package=Coreset
to link to this page.