Research On Approximation Algorithms For K-Means Problem With Penalties And K-Center Problem With Constraints

The clustering problem is a classical problem with more than 60 years of research history,and has attracted the attention of many scientists in the fields of machine learning,combinatorial optimization,data analysis,image processing,etc.It is still a hot problem in artificial intelligence today.The input of the classical clustering problem is the data points on the metric space,and our goal is to find the best set of centers according to the objective function corresponding to different problems,and then classify the data points into different classes by assigning each data point to its nearest center.The most representative problems in clustering are the k-means and k-center problems.The k-means and k-center problems are NP-hard problems,so heuristics and approximation algorithms are often designed to solve them.Since the k-means and k-center problems are encountered in a variety of situations in practice,different definitions of distance or different optimization objective functions may be used for different situations,which leads to a variety of deformation problems associated with the k-means and k-center problems.In today’s artificial intelligence era,many decisions are usually made by intelligent algorithms alone without human review,which usually raises fairness and privacy issues,and thus the study of clustering with privacy and fairness constraints is also an important direction.In this thesis,we study the deformation,fairness and privacy issues of the clustering problem,and our main work is as follows:Chapter 2 studies the fixed-dimensional k-means problem with penalties.In this problem,the spatial dimension of the input data points is constant,and some data points can be unassigned to the centers during the clustering process,but at a cost.A polynomial time approximation scheme for this problem is given using local search techniques,and the associated approximation ratio and time complexity of the algorithm are proved.Chapter 3 studies the stable instances of the k-means problem with penalties in fixeddimensional Euclidean space.An instance is said to be a stable instance of the original problem if the optimal solution of the instance remains the same as the optimal solution without perturbation when the metric and penalty functions of the instance are perturbed.The exact algorithm for this problem is given by using the local search technique for rational partitioning of the solution,and we prove the properties of the partitioning technique and the time complexity of the algorithm.Chapter 4 studies several k-center problems in the differential privacy framework,proposes corresponding privacy algorithms for these problems using exponential mechanisms,greedy algorithms,and distributed algorithms,and we prove the algorithms’ associated approximation ratios and time complexities.Chapter 5 studies the k-center problem with fairness constraints,giving 4-approximation algorithm for the k-center problem with outliers and fairness constraints,and 18-approximation algorithm for the distributed k-center problem with outliers and fairness constraints.The algorithms make use of maximum matching algorithm,greedy algorithm,distributed clustering algorithm,etc.,and we prove the relevant approximation ratio and time complexity of the algorithms.