Facility location problem

The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors' facilities. The techniques also apply to cluster analysis. Minimum facility location A simple facility location problem is the Weber problem, in which a single facility is to be placed, with the only optimization criterion being the minimization of the weighted sum of distances from a given set of point sites. More complex problems considered in this discipline include the placement of multiple facilities, constraints on the locations of facilities, and more complex optimization criteria. In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be opened, and a set of demand points D that

Algorithms For Clustering Problems

Ashkan Norouzi Fard

Clustering is a classic topic in combinatorial optimization and plays a central role in many areas, including data science and machine learning. In this thesis, we first focus on the dynamic facility location problem (i.e., the facility location problem in evolving metrics). We present a new LP-rounding algorithm for facility location problems, which yields the first constant factor approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on clients and facilities, and connects every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP-roundings for facility location problems. In particular, we use \emph{no clustering} and we enable clients to connect through paths of \emph{arbitrary lengths}. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem. Furthermore, we present both empirical and theoretical aspects of the

k

-means problem. The best known algorithm for

k

-means with a provable guarantee is a simple local-search heuristic that yields an approximation guarantee of

9+\epsilon

, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that enables us (1) to exploit the geometric structure of

k

-means and (2) to satisfy the hard constraint that at most

k

clusters are selected without deteriorating the approximation guarantee. Our main result is a

6.357

-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of

k

-means where the underlying metric is not required to be Euclidean and for

k

-median in Euclidean metrics. We also improve the running time of our algorithm to almost linear running time and still maintain a provable guarantee. We compare our algorithm with {\sc K-Means++} (a widely studied algorithm) and show that we obtain better accuracy with comparable and even better running time.

EPFL2018

Dynamic Facility Location via Exponential Clocks

Hyung Chan An, Ashkan Norouzi Fard, Ola Nils Anders Svensson

The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the "stability" of the solution: There is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches. We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on the clients and facilities and connects every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP roundings for facility location problems. In particular, we use no clustering and we allow clients to connect through paths of arbitrary lengths. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem.

Association for Computing Machinery2017

Algorithms For Clustering Problems

Ashkan Norouzi Fard

k

-means problem. The best known algorithm for

k

-means with a provable guarantee is a simple local-search heuristic that yields an approximation guarantee of

9+\epsilon

, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that enables us (1) to exploit the geometric structure of

k

-means and (2) to satisfy the hard constraint that at most

k

clusters are selected without deteriorating the approximation guarantee. Our main result is a

6.357

-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of

k

-means where the underlying metric is not required to be Euclidean and for

k

EPFL2018

Optimal placement of bracings for seismic retrofit of building frames

Algorithms For Clustering Problems

Dynamic Facility Location via Exponential Clocks

Algorithms For Clustering Problems

Dynamic Facility Location via Exponential Clocks

Optimal placement of bracings for seismic retrofit of building frames