LELECUT type triple patterning lithography is one of the most promising techniques in 14 nm logic node and beyond. To prevent yield loss caused by overlay error, LELECUT mask assignment, which is tolerant to overlay error, is desired. We propose a method that obtains a LELECUT assignment that is tolerant to overlay error. The proposed method uses positive semidefinite relaxation and randomized rounding technique. In our method, the cost function that takes the length of boundary of features determined by the cut mask into account is introduced.