Understanding PAM - why is it greedy?

Question

I've been studying k-medoids for a while but i can't understand the first step or BUILD step: in particular i can't get how the initial medoids would be "greedy". I'm not much confident with the theory behind this notion but i can guess what does it mean. I understand from other answers in here that first medoid is chosen as the medoid of the whole dataset and this is "greedy", but how about the other $k-1$? I really can't consider random choice of the other medoids as "greedy". So my question is about how the initial $k$ medoids are picked, except the random choice k-means like. And then, is it right to consider PAM an approximation of k-medoids problem that performs a greedy search (that provides an approximate solution, of course)?

Answer 1

Greedy is not random. Greedy means no backtracking:

https://en.wikipedia.org/wiki/Greedy_algorithm

Greedy choice property

We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices.

BUILD seems to make the "current best" decision, but never reconsiders this choice until the second SWAP algorithm later.

You may want to read up on this in p-medians literature which is less applied and more optimization theory oriented.