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 decisio n version of this question is known to be NP-complete. We present two appro ximation algorithms for the optimization version of this question. We first prove that the greedy algorithm achieves a factor of 1/3. We then use insi ghts derived from the linear relaxation of an integer program to obtain an algorithm based on matchings that achieves a better performance guarantee o f 1/2. These are the first known polynomial-time approximation algorithms f or the latin square completion problem that achieve nontrivial worst-case p erformance guarantees. Our study is motivated by applications to lightpath assignment and switch configuration in wavelength routed multihop optical n etworks.