In this paper we present and analyze a model for clustering in networks that offer Software as a Service (SaaS). In this problem, organizations requesting a set of applications have to be assigned to clusters such that the costs of opening clusters and installing the necessary applications in clusters are minimized. We prove that this problem is NP-hard, and model it as an Integer Program with symmetry breaking constraints. We then propose a Tabu search heuristic for situations where good solutions are desired in a short computation time. Extensive computational experiments are conducted for evaluating the quality of the solutions obtained by the IP model and the Tabu Search heuristic. Experimental results indicate that the proposed Tabu Search is promising.

Additional Metadata
Keywords Tabu Search, complexity theory, integer programming, software as a service
JEL Business Administration and Business Economics; Marketing; Accounting (jel M), New Firms; Startups (jel M13), Management of Technological Innovation and R&D (jel O32)
Publisher Erasmus Research Institute of Management (ERIM)
Persistent URL
van der Gaast, J.P, Rietveld, C.A, Gabor, A.F, & Zhang, Y. (2011). A Local Search Algorithm for Clustering in Software as a Service Networks (No. ERS-2011-004-LIS). ERIM report series research in management Erasmus Research Institute of Management. Erasmus Research Institute of Management (ERIM). Retrieved from