An improved approximation algorithm for the partial Latin square extension problem

An improved approximation algorithm for the partial Latin square extension problem

0.00 Avg rating0 Votes
Article ID: iaor20051119
Country: Netherlands
Volume: 32
Issue: 5
Start Page Number: 479
End Page Number: 484
Publication Date: Sep 2004
Journal: Operations Research Letters
Authors: , ,
Keywords: programming: assignment
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 integer programming (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.

Reviews

Required fields are marked *. Your email address will not be published.