Exact discrete k-centre optimum

ExactKCentre() finds an optimal solution to the discrete k-centre problem.

Usage

ExactKCentre(k, d, maxSeconds = 60)

ExactKCenter(k, d, maxSeconds = 60)

Arguments

k: Integer specifying maximum number of centres to identify, from 1 to nrow(d).
d: dist object or a square symmetric numeric distance matrix.
maxSeconds: Numeric specifying wall-clock budget, in seconds, for the search. If the time expires before the optimum is proven, the smallest radius proven feasible is returned, with the attribute proven = FALSE.

Value

ExactKCentre() returns an integer vector of length \(\le k\) listing the chosen centres in ascending order. It has class c("KCentreExact", "KCentreSelection") and attributes:

radius: The covering radius achieved; the proven optimum when proven is TRUE, otherwise an upper bound.
proven: Logical: TRUE if optimality is certified.
seconds: Wall-clock seconds elapsed.
N, k: Instance size and centre budget.

Details

The optimum covering radius is the smallest threshold r, over the achieved distinct distances, for which k centres can cover every point within r.

Each probe asks whether k centres cover every point within a candidate radius. This is decided combinatorially via unit propagation and dominance reduction, then an exhaustive component-wise search. The search is warm-started from the KCentre() radius, then bisects downwards.

Progress bar

In interactive sessions, a progress indicator is shown. To toggle, set options("Coreset.progress" = FALSE) (or TRUE).

Examples

set.seed(1)
pts <- matrix(rnorm(40), ncol = 2)
d <- dist(pts)
ExactKCentre(3L, d)
#> 3 centres (3 11 15) by exact cover search, proven optimal, covering radius = 1.385