When does pam (partition around medoids) fails to find the optimal solution? (counter example?!) If I understand correctly, the pam algorithm is a greedy search for a set of medoids such that no other set offers a lower cost (i.e.: the sum of distances of points to their nearest medoid).
However, when does the pam algorithm fail? Are there general cases for which it is known to reach the global optimum? (say, for some ratio of k and n?)
Are there nice counter examples demonstrating when some set of medoid is stable (i.e.: would lead pam to converge), but sub optimal?
 A: Clustering is an NP-complete problem - see proof fo the one definition of clustering and another definition of clustering.
The question of whether P=NP wasn't answered yet but is seems as if the complexity classes are different.
If it is so, then no polynomial time algorithm, like the pam algorithm can solve the problem.
When facing an NP-complete problem we can cope with it by looking for approximation algorithms. The one bellow has approximation ratio of 2.

Gonzalez, T. F. (1985), 
  ``Clustering to minimize the maximum intercluster distance'', 
  Theoretical Comput. Sci. 38, 293-306.

However, pam goes in a different direction and it is a randomized greedy algorithm. 
Hence, it looks for an optimal solution but I guess that usually it fails and finds a local optimum. 
It seems that pam fails on the regular cases that are hard to k-means.
On slide 24 there is a example that is hard for k-means like algorithms but 
DBSCAN clusters well.
A: Try to build one!
We need a cluster assignment that is stable, but not optimal.
So the medoids bust be the medoids of their clusters, and every object is assigned to its closest medoid. But there is a solution that is a lot better.
Lets start simple. One dimensional, three points per cluster, stars indicate the cluster centers.
Data: 1 2 3     6 7 8
Sol1:   *         *

Now let's modify this by moving one object away from the center.
Data:1 2 3     6 7                 15
Sol1:  *         *
Sol2:    *                         *

The cost of Sol2 is 2+1+0+3+4+0=10. But it's hard to get there. Most likely PAM will get stuck in the first solution, which costs 1+0+1+1+0+8=11. If it doesn't, you may need to increase the spacing of the clusters, or move the outlier.
Example of R code for the above example:
> pam(c(1:3,6,7,15), k = 2, medoids = c(2,5))$med
     [,1]
[1,]    2
[2,]    7

> pam(c(1:3,6,7,15), k = 2, medoids = c(2,6))$med
     [,1]
[1,]    3
[2,]   15

