Clustering and Facility Location Problems

Facility location problems arise in a wide range of applications such as plant or warehouse location problems and network design problems, and have been widely studied in Computer Science and Operations Research literature. These problems typically involve an underlying set F of facilities that provide service, and an underlying set D of clients that require service, which need to be assigned to facilities in a cost-effective fashion. This abstraction is quite versatile and also captures clustering problems, where one typically seeks to partition a set of data points into k clusters, for some given k, in a suitable way, which themselves find applications in data mining, machine learning, and bioinformatics.  Basic variants of facility location problems are now relatively well-understood, but we have a much-less understanding of more-sophisticated models that better model the real-world concerns. In this talk, I will present my work on some of these models inspired by some real-world optimization scenarios and give an overview of techniques that have been successfully improved the state-of-the-art approximation algorithm for these models. I will discuss some future directions and open problems as well.

See more at https://www.microsoft.com/en-us/resea...