Center-based clustering is a set of clustering problems that require finding a single element, a center, to represent an entire cluster. The algorithms that solve this type of problems are very efficient for clustering large and high-dimensional datasets. In this paper, we propose a similar heuristic used in Lloyd’s algorithm to approximately solve (EMAX algorithm) a more robust variation of the k-means problem, namely the EMAX problem. Also, a new center-based clustering algorithm (SSO-C) is proposed, which is based on a swarm intelligence technique called Social Spider Optimization. This algorithm minimizes a multi-objective optimization function defined as a weighted combination of the objective functions of the k-means and EMAX problems. Also, an approximation algorithm for the discrete k-center problem is used as a local search strategy for initializing the population. Results of the experiments showed that SSO-C algorithm is suitable for finding maximum best values, however EMAX algorithm is better in finding median and mean values.