Approximating Latin Square Extensions

In this paper we investigate the problem of computing the maximum number of entries which can be added to a partially filled latin square. The decision version of this question is known to be NP-complete. We present two approximation algorithms for the optimization version of this question. We first prove that the greedy algorithm achieves a factor of 1/3. We then use insights derived from the linear relaxation of an integer program to obtain an algorithm based on matchings that achieves a better performance guarantee of 1/2. These are the first known polynomial-time approximation algorithms for the latin square completion problem that achieve nontrivial worst-case performance guarantees. Our study is motivated by applications to lightpath assignment and switch configuration in wavelength routed multihop optical networks. Received September 25, 1997; revised February 16, 1998.