Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Approximating Latin Square Extensions
| |
|
Approximating Latin Square Extensions
S. R. Kumar1, A. Russell2 and R. Sundaram3
| (1) |
Department of Computer Science, Cornell University, Ithaca, NY 14853, USA. ravi@cs.cornell.edu., US |
| (2) |
Department of Mathematics, M.I.T., Cambridge, MA 02139, USA. acr@math.mit.edu., US |
| (3) |
Laboratory for Computer Science, M.I.T., Cambridge, MA 02139, USA. koods@theory.lcs.mit.edu., US |
Abstract. 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.
Key words. Latin squares, Optical switch configuration, Approximation algorithms.
Received September 25, 1997; revised February 16, 1998.
Fulltext Preview (Small, Large)
|
|
|
|
|
|