MAX-SNP hardness of MIN-PC and MASC-GP(n) problems
M. I. Poberii · Pattern Recognition and Image Analysis · 2011
It is known that the problem on the minimal covering of a finite number of points in a plane by a set of straight lines (MIN-PC) and the problem on the minimal affine separating committee formulated in a fixed dimension space within n > 1 (MASC-GP( n )) are NP-hard in the strong sense. In the present work, it is shown that these problems are MAX-SNP-hard.