\input zb-basic
\input zb-ioport
\iteman{io-port 01310396}
\itemau{Kumar, S.R.; Russell, A.; Sundaram, R.}
\itemti{Approximating latin square extensions.}
\itemso{Algorithmica 24, No.2, 128-138 (1999).}
\itemab
Summary: 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\over 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\over 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.
\itemrv{~}
\itemcc{}
\itemut{greedy algorithm}
\itemli{doi:10.1007/PL00009274}
\end