I've been doing a lot of clustering work lately and have been using the PAM algorithm.
Based on my research it appears to be deterministic because the initialization of medoids are selected from items in the dataset (selected randomly). Further, subsequent medoids in the SWAP stage are also items from the dataset. Therefore, for any given dataset there is only one correct answer that minimizes the sum of the absolute distances to their cluster medoid.
Thus, PAM is an exhaustive search of every element for the optimal k medoids.
In comparison the k-means algorithm picks an arbitrary synthetic starting point for the cluster centers. The centers move until until the error is optimally reduced.
Am I correct in this assumption?