Coreset
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.
- A simple and effective algorithm for the MaxMin diversity problem
- An integer programming approach for solving the p-dispersion problem
- Approximation Algorithms for the Vertex K-Center Problem: Survey and Experimental Evaluation
- Clustering to minimize the maximum intercluster distance
- Determinantal point processes for machine learning
- GRASP and path relinking for the max-min diversity problem
- Maximum entropy sampling
- Tabu search guided by reinforcement learning for the max-mean dispersion problem
- When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem
This page was built for software: Coreset
