Accelerating the Local Search Algorithm for the Facility Location

摘要

This paper presents several methods to significantly speed up the local search algorithm for the facility location clustering. Most papers regarding the facility location focus on the mathematical theory, tight approximation ratios, and solid proofs. While this is certainly important, the papers rarely concern the practical application of the proposed algorithms. A straightforward, naive approach is often not efficient, so special techniques must be used to achieve high performance. This paper focuses on an acceleration of the local search algorithm. Specially, it proposes an acceleration using a space partitioning and a parallelisation on a desktop computer.