Local search algorithm for the compacted cells area problem
Davin Chia, Andrew E. B. Lim · 2002
The minimum area joining of k compacted cells problem is an open problem that is not known whether to be polynomial-time solvable or NP-hard. In this paper we derive a divide-and-conquer approach for determining a lower-bound on the optimal cost of large problems. We also devise a taboo search algorithm whose performance can be measured and evaluated for large cases by using the derived lower bounds. Experimental results suggest that the algorithm performs reasonably well.