The First Approximation Algorithm for the Maximin Latin Hypercube Design Problem

Abstract

In metamodeling, the choice of sampling points is crucial for the quality of the model. In this context, the maximin Latin hypercube designs (LHD), with their space-filling and noncollapsing properties, are particularly efficient. To this day, there is no polynomial time algorithm that produces optimal maximin LHDs, i.e., in which the minimum distance between two points (the separation distance) is maximal. We are interested in LHDs with a separation distance as large as possible. The algorithm we propose, IES, gives an approximate solution to the LHD problem regardless of its dimension and size with a theoretical performance guarantee. We introduce two upper bounds for the separation distance to find its approximation ratio. Its performance is compared with the best metaheuristic algorithm known for this problem, an appropriate simulated annealing scheme. Our algorithm defeats the metaheuristic algorithm for large instances of the problem while having a very short running time.