Evolutionary algorithms (EAs) have been widely studied in numerical experiments and successfully applied in practice. However, most existing EAs are designed without a theoretical analysis for their performance guarantee. In this paper, we define a fitness function to guide the well-known (1+1) evolutionary algorithm, called (1+1) EA, to optimize the NP-hard k -median problem. We prove that the (1+1) EA can obtain a performance guarantee of 5 for k -median problem in polynomial expected runtime O (m n 2 ⋅ d m a x) if all distances between data points and cluster centers are integers, where m and n are respectively the cardinalities of the data set and cluster center set, and d m a x denotes the largest distance between data points and cluster centers. To tackle the general case that the distances between data points and cluster centers are real number, we propose an improved (1+1) EA, which employs a distance scaling scheme during the evolutionary process. Our rigorous theoretical analysis shows that the improved (1+1) EA obtains a performance guarantee of 5 + ε in expected runtime O (ε − 1 m n 2 log (m ⋅ d m a x)) , where ε > 0 is a constant. This study reveals that an appropriate scaling scheme can help EAs to obtain a constant performance guarantee in polynomial expected runtime and provides insights into design EAs for some NP-hard problems. In addition, we conduct experiment to compare the efficiency of the improved (1+1) EA with three clustering algorithms on optimizing three UCI datasets. • We define a new fitness function to guide the (1+1) EA to solve the k-median problem. • We propose an improved (1+1) EA for the k-median problem with performance guarantee. • We show that a proper scaling scheme helps EA to obtain constant approximation ratio. [ABSTRACT FROM AUTHOR]