RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2010 Volume 16, Number 3, Pages 210–216 (Mi timm593)

This article is cited in 2 papers

On the belonging of the problems MIN-PC and MASC-GP$(n)$ to the class of MAX-SNP-hard problems

M. I. Poberii

Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences

Abstract: 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 space of fixed dimension (MASC-GP$(n)$) are NP-hard in the strong sense. We show that these problems are MAX-SNP-hard.

Keywords: computational complexity, strong NP-hardness, covering of points, affine committee.

UDC: 519.6

Received: 22.03.2010



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025