An improved approximation algorithm for the partial Latin square extension problem

✍ Scribed by Carla P. Gomes; Rommel G. Regis; David B. Shmoys

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 203 KB
• Volume: 32
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/j.orl.2003.09.007

✦ Synopsis

The problem of completing partial latin squares arises in a number of applications, including conflict-free wavelength routing in wide-area optical networks, statistical designs, and error-correcting codes. A partial latin square is an n by n array such that each cell is either empty or contains exactly one of the colors 1,...,n, and eadL color occurs at most once in any row or column. In this paper, we consider the problem of finding an extension of a given partial latin square with the maximum nmnber of colored cells. Approximation algorithms for this problem were introduced by Kumar, Russell, aml Sundaram, who gave a 2-approximation algorithm for this problem that is based on a 3-dimensional assignment formulation. We introduce a packing linear programming relaxation for this problem, and show that a natural randomized rounding algorithm yields an e/(e -1)-approximation algorithm.