Supplementary material for: Sorting Points Into Neighborhoods (SPIN): Data Analysis and Visualization by Ordering Distance Matrices
Dan Tsafrir, Ilan Tsafrir, Liat Ein‐Dor, Or Zuk, Eytan Domany · 2005
Table 1 summarizes the parameters and running times for some examples given in this article. The results may depend on the starting permutation and several restarts are sometimes needed to find the global minimum. However, one of the strengths of SPIN is that from a practical point of view, convergence to the global minimum is often not necessary. In most cases the local minima reached by SPIN are almost as informative for extracting structural information. Proofs for the STS algorithm Complexity We prove that the STS problem is NP-Complete by finding a reduction from the STS problem to the well known, NP-complete, problem of proving that a graph contains a clique of size k [Garey and Johnson, 1979]. Let G = be an (undirected) graph on n vertices. Define D as follows: