Problème de l'emplacement d'installations

Le problème d'emplacement d'installations (facilities location problem) est un problème de recherche opérationnelle et de géométrie algorithmique. Il consiste à répondre à la question : : Quel est le meilleur emplacement pour une installation, ou pour un ensemble d'installations. Origine du problème Le terme « installation » peut désigner un atelier, une usine, un service public (service postal, hôpital, Caserne de pompiers...), un commerce, un entrepôt (stock)… Le terme « meilleur » signifie en général « qui a le plus court trajet » (d'un client vers un service, d'une usine vers une autre, d'un stock vers un commerce, d'un véhicule de secours vers le lieu du sinistre), « qui assure le service attendu avec le plus petit nombre d'installations », « qui coûte le moins cher » ou bien « qui éloigne le danger » (usine ou stock de type Seveso par rapport à des agglomérations, commerce concurrent avec risque de saturation du marché local). La méthode s'applique également au part

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

Problème de l'emplacement d'installations

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