Discrete Facility Location in Machine Learning

Authors:
Publisher website
Google Scholar
Abstract
Facility location problems form a broad class of optimization problems extremely popular in combinatorial optimization and operations research. In every facility location problem, one must locate a set of facilities in order to satisfy the demands of customers so as some certain objective function be optimal. 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 we need to partition a set of customers into clusters assigned to open facilities. In this survey we briefly look at how the 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 of exact methods and heuristics, as well as some extensions of the basic problems and algorithms in applied machine learning tasks. Note that the main emphasis lies here on discrete facility location problems which, for example, underlie many widely used clustering algorithms (PAM, affinity propagation, etc.). Since the high computational complexity of the 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 these large data collections.

This publication has 118 references indexed in Scilit: