Discrete facility location in machine learning

Facility location problems form a wide class of optimization problems, extremely popular in combinatorial optimization and operations research. In any facility location problem, one must locate a set of facilities in order to satisfy the demands of customers so as a certain objective function is optimized. Besides numerous applications in public and private sectors, the problems are widely used in machine learning. For example, clustering can be viewed as a facility location problem where one needs to partition a set of customers into clusters assigned to open facilities. In this survey we briefly look at how ideas and approaches arisen in the field of facility location led to modern, popular machine learning algorithms supported by many data mining and machine learning software packages. We also review the state-of-the-art exact methods and heuristics, as well as some extensions of basic problems and algorithms arisen in applied machine learning tasks. Note that the main emphasis here lies on discrete facility location problems, which, for example, underlie many widely used clustering algorithms (PAM, affinity propagation, etc.). Since the high computational complexity of conventional facility location-based clustering algorithms hinders their application to modern large-scale real-life datasets, we also survey some modern approaches to implementation of the algorithms for such large data collections. Bibliogr. 138.