Approximation Algorithms For Facility Location Problems With Nth Power Metric And Penalties And Correlation Clustering Problems

Location problem,a classical problem in the field of operations research,has been widely applied in production,logistics management,network design and so on.The facility location problem and k-median problem are two basic location problems.As clustering problems,these two problems also play an important role in the field of data mining.Correlation clustering is another clustering problem which is suitable to the case that the number of clusters is unknown.These problems are NP-hard.There are many researches of approximation algorithms for these problems.This paper studies some variants of the facility location problem and correlation clus-tering problem,including the nth power metric facility location problem with linear penalties,k-facility location problem with linear penalties,squared metric k-facility location problem,and weighted correlation clustering problem.We use the techniques of linear programming rounding,local search,and semi-definite programming rounding,to give the approximation al-gorithms for these problems,and the analyzes of approximation ratios.In the nth power metric facility location problem with linear penalties(MnFLPLP),the connection costs between facilities and clients are nth power metric(that is,they satisfy the non-negativity,symmetry,and nth power triangle inequalities).If a client is not serviced by any facility,it must pay a penalty cost.The linear penalties mean that the total penalty cost of a solution equals to the sum of penalty costs paid by all client.This problem is a general-ization of the metric facility location problem,implying it is NP-hard.We apply the 1.5148-approximation algorithm for the metric FLPLP to MnFLPLP,and arrive at an implicit approxi-mation ratio.Through numerical computation,we obtain the constant approximation ratios for n = 2,…,10,and the curves of bi-factor approximation ratio for n = 2 and 10.We observe that smaller n has smaller gap between the approximation ratio and its lower bound.Further-more,The curve of bi-factor approximation ratio is very close to the lower bound on some region.In the k-facility location problem with linear penalties(k-FLPLP),the connection costs between facilities and clients are metric(that is,they satisfy the non-negativity,symmetry,and triangle inequalities).The problem has linear penalty cost and the cardinality constraint for facility(that is,the number of opened facilities is at most a given constant k).This problem is a generalization of the classical facility location problem and k-median problem,implying it is NP-hard.We applied the local search algorithm with the add,delete,and swap local operations,to k-FLPLP.In the analysis of the algorithm,we view the penalty for clients as a dummy facility,so that it can be considered in the local operations.We prove the approximation ratio of the local search algorithm is 2 +(?)+ ? which is the same as that of k-FLP,implying the penalty cost has no effect on the performance guarantee for this local search algorithm.The third variant is the squared metric k-facility location problem.In this problem,the facilities and clients are in a metric space,and the connection cost between a facility and a client is equal to the square of their distance.The differences to the MnFLPLP are the penalty cost and the cardinality constraint.This problem is a generalization of k-FLP,implying it is also NP-hard.We use the techniques of local search and scaling to give a(22+(?)+ ?)-approximation algorithm for this problem.From the numerical experiments,we observe that the local search algorithm has a good performance in practice.The last problem we study is the weighted correlation clustering problem.In this problem,there are two types of weight for each edges which indicate the positive and negative correla-tions respectively.The objective is maximizing agreements,that is,maximizing the sum of the weights with positive correlation for the edges in a same cluster,and the sum of the weights with negative correlation for the edges in the cut set.This problem is NP-hard.We improve the 0.75-approximation algorithm by using the technique of outward rotation.The outward rotation makes us to obtain the approximation ratios for different classes of instances.It can not improve the approximation guarantee for the worst case,however,it has good performance for lots of instances.