A maximum matching based heuristic algorithm for partial Latin square extension problem

A partial Latin square (PLS) is an assignment of n symbols to an n × n grid such that, in each row and in each column, each symbol appears at most once. The partial Latin square extension (PLSE) problem asks to find such a PLS that is a maximum extension of a given PLS. The PLSE problem is NP-hard, and in this paper, we propose a heuristic algorithm for this problem. To design a heuristic, we extend the previous 1 over 2-approximation algorithm that utilizes the notion of maximum matching. We show the empirical effectiveness of the proposed algorithm through computational experiments. Specifically, the proposed algorithm delivers a better solution than the original one and local search. Besides, when computation time is limited due to an application reason, it delivers a better solution than IBM ILOG CPLEX, a state-of-the-art optimization solver, especially for large scale “hard” instances.