@article{oai:barrel.repo.nii.ac.jp:00005044,
 author = {Haraguchi, Kazuya},
 journal = {Lecture Notes in Computer Science},
 month = {Apr},
 note = {A partial Latin square (PLS) is a partial assignment of nsymbols to an n×n grid such that, in each row and in each column, eachsymbol appears at most once. The partial Latin square extension problemis an NP-hard problem that asks for a largest extension of a givenPLS. In this paper we propose an efficient local search for this problem.We focus on the local search such that the neighborhood is defined by(p, q)-swap, i.e., removing exactly p symbols and then assigning symbolsto at most qempty cells. For p ∈ {1, 2, 3}, our neighborhood search algorithmfinds an improved solution or concludes that no such solutionexists in O(np+1) time. We also propose a novel swap operation,Trellisswap,which is a generalization of (1, q)-swap and (2, q)-swap. Our Trellisneighborhoodsearch algorithm takes O(n3.5) time to do the same thing.Using these neighborhood search algorithms, we design a prototype iteratedlocal search algorithm and show its effectiveness in comparisonwith state-of-the-artoptimization solvers such as IBM ILOG CPLEX and LocalSolver.},
 pages = {182--198},
 title = {An Efficient Local Search for Partial Latin Square Extension Problem},
 volume = {9075},
 year = {2015}
}