Local Search Algorithms For Capacitated Facility Location And K-means Problems

The facility location and k-means problems are classical NP-hard problems.They have been attracting research from both domestic and overseas researchers in theoretical computer science and combinatorial optimization areas.The facility location problem is aim to search for reasonable assignment of required task so as to achieve optimal solution to some degree.It is not only applied widely in factories or network facilities location,but also invoked by other algorithms as it is one of the basic clustering problems.For these reasons,theoretical com-puter science,discrete combinatorial mathematics,operational research,engineering science and management science pay much attention to facility location problems.In practical,the clas-sical facility location problem extend so many general models such as uncapacitated facility location problems,capacitated facility location problems,k-facility location problems and so on where the capacitated facility location problems include both hard and soft ones.The k-means problem originates from signal processing and widely applied in data mining,machine learning and artificial intelligence areas.At the same time,it attracts research from theoretical computer science as well as statistics and optimization areas because it is also one of the most classical clustering problems.The k-means clustering is popular till now as one of the most significant and easiest methods of clustering analysis from the 60s of last century.And it is employed widely by algorithms in machine vision,geostatistics,astronomy,agriculture and so on.It made great progress in theoretical research in last decades.However,in the environment of leapfrog technologies and big data,what we meet today in practical varies from that in old days in diversity,complexity and quantity.That is why the k-means algorithms need further studies.The local search technique is one of the most useful methods in approximation algorithm design in many classical problems,such as the traveling salesmen problem,Steiner tree prob-lem,scheduling problem,knapsack problem,bin-packing problem,satisfaction problem and so on.The local search algorithm is originally known as a heuristic algorithm for optimization problems.It is popular in engineering and manufacturing because of its advantages such as fast convergence,construction revelation and combination.Motivated by local search technique,we study some of the facility location and k-means problem and obtain several approximation al-gorithm results.Particularly,what we choose in facility location problem is so called universal facility location problem with linear penalties.This problem is a generalization of universal facility location which itself is a generalization of classical facility location and hard/soft ca-pacitated facility location problems.Thus the universal facility location problem with linear penalties is at least NP-hard.In this problem,some part of the clients' demand need not be sev-ered,but we will a penalty item to the object function which is a linear function with respect to the unsevered demand.So we aim to achieve a balance of facility cost,service cost and penalty cost in this problem.What we choose in k-means is a kind of k-means problem with facility cost,that is to say,we do not simply count the number of potential centers but count the weighted number of it which varies according to its location(we called facility/opening cost).So what we want to achieve is a balance point of facility cost and connection cost of other observations.This paper mainly contains 5 results and the body mainly contains 3:a(7.88 + ?)-approximation as well as a(5.83 + ?)-approximation algorithm for the universal facility location problem with linear penalties and a(13+?)-approximation algorithm for the k-means with facil-ity cost.Besides,the introduction part contains 2 survey on algorithms for the k-means problem and its variants.