Deterministic Methods to Initialize K-Means and K-Medoids Clustering Methods

Question

I am looking for effective and deterministic methods to initialize K-Means and K-Medoids algorithms.

There is a great answer in Methods of initializing K-Means Clustering yet most of them has some randomness into them.

I created some methods based on the idea of the farthest point from a set of samples. Some variants on the idea in the following code:

function [ vIdx ] = Method3( mD, numPts )
% Selects the sample which maximizes the Median Distance. Then iterative
% finds the samples which have the maximum minimal distance to any of
% the chosen samples.

numSamples = size(mD, 1);

vIdx    = zeros(numPts, 1);
vMinVal = zeros(numSamples, 1);

[~, vIdx(1)] = max(median(mD));

for ii = 2:numPts
    vMinVal(:)  = min(mD(:, vIdx(1:(ii - 1))), [], 2);
    [~, maxIdx] = max(vMinVal);
    vIdx(ii)    = maxIdx;
end


end

Where mD is the pair wise distance matrix of the data.

I also saw the method - A Simple and Fast Algorithm for K-Medoids Clustering:

function [ vIdx ] = InitMedoidsCenterMass( mD, numCentroids )
% See A Simple and Fast Algorithm for K-Medoids Clustering - https://doi.org/10.1016/j.eswa.2008.01.039.

numSamples  = size(mD, 1);

vV = zeros(numSamples, 1);

for jj = 1:numSamples
    for ii = 1:numSamples
        vV(jj) = vV(jj) + (mD(ii, jj) / sum(mD(ii, :)));
    end
end

[~, vIdx] = mink(vV, numCentroids);


end

Yet it performed poorly in my data set.

I am looking for more approaches which their input is mD (So they can handle any kind of distance metric) and are effective.