An improved approximation algorithm for the partial Latin square extension problem
2004; Elsevier BV; Volume: 32; Issue: 5 Linguagem: Inglês
10.1016/j.orl.2003.09.007
ISSN1872-7468
AutoresCarla P. Gomes, Rommel G. Regis, David B. Shmoys,
Tópico(s)Complexity and Algorithms in Graphs
ResumoPrevious 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.
Referência(s)