M. Yu. Khachai, M. I. Poberii, “The computational complexity and approximability of a series of geometric covering problems”, Trudy Inst. Mat. i Mekh. UrO RAN, 2012, Volume 18, Number 3,Pages <nobr>247

This article is cited in 3 papers

The computational complexity and approximability of a series of geometric covering problems

M. Yu. Khachai^ab, M. I. Poberii^b

^a Ural Federal University
^b Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences

Abstract: We consider a series of geometric problems on the covering of finite subsets of finite-dimensional numerical spaces by minimal families of hyperplanes. We prove that the problems are hard and Max-SNP-hard.

Keywords: $NP$-complete problem, polynomial-time reduction, Max-SNP-hard problem, $L$-reduction, polynomial-time approximation scheme (PTAS).

UDC: 519.6

Received: 26.03.2012