Bound on swap steps and its relation to NPHardness #69
Description
If we could reduce the number of swap steps, T, to be polynomial in N, and we could also select polynomial subset of initial conditions (BUILD), from which the SWAP algorithm is gauranteed to find the global optimum, we would have a polynomial time algorithm for performing the combinatorial optimization which is NP-hard, and thus proving P = NP. Not likely.
In the specific case of Gaussian Mixture Model, it may be possible to do this, though; assume k is chosen appropriately, to be the number of clusters. Then each cluster has to have exactly 1 medoid. So the possible intitial conditions are (N/k)^k. And, from other ideas we've discussed, number of swap steps will be <N.
Perhaps you could choose absolutely ANY point in each cluster -- say the first point of each cluster. Then you have an algorithm to do the combinatorial optimization in just <= N steps.
It may be possible to simplify the techniques here using the reduction of BUILD to SWAP.
Think about this some more....