A Local Search Algorithm For Hard Uniform Capacitated K-facility Location Problem

The facility location problem is one of the widely studied problems in com-binatorial optimization and computer science with a large variety of application-s, such as telecommunication network design, artificial intelligence and machine learning, etc. Numerous approximation algorithms have been proposed for solv-ing the problem since it is known to be NP-hard. In this thesis, we consider the uniform hard capacitated k-facility location problem, which is a very difficult problem in facility location, since two kinds of hard constraints appear together:the cardinality and the capacity constraints. We focus our attention on the com-binatorial algorithm by using local search techniques. For any constant ? > 0,we proposed a (9 +?) approximation algorithm by opening at most (3 + ?)k facilities, where ? is a constant, as long as its value > ?54+6??/?. We also give the rigorous analysis and proof of this algorithm.