|
|||||
|
|
An improved approximation algorithm for the partial Latin square extension problem |
|
| Authors: | Carla P. Gomes Rommel G. Regis David B. Shmoys |
| Affiliation: | a Department of Computer Science, Cornell University, Ithaca, NY 14853, USA b School of Operations Research & Industrial Engineering, Cornell University, Ithaca, NY 14853, USA c School of Operations Research & Industrial Engineering and Department of Computer Science, Cornell University, Ithaca, NY 14853, USA |
| Abstract: | Previous work on the partial Latin square extension (PLSE) problem resulted in a 2-approximation algorithm based on the LP relaxation of a three-dimensional assignment IP formulation. We present an e/(e−1)-approximation algorithm that is based on the LP relaxation of a packing IP formulation of the PLSE problem. |
| Keywords: | Latin square Randomized rounding Approximation algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ | |