The computational complexity and approximability of a series of geometric covering problems / Khachai M. Yu.,Poberii M. I. // PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS. - 2013. - V. 283, l. 1. - P. 64-77.

ISSN/EISSN:

0081-5438 / 1531-8605

Type:

Article

Abstract:

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

Author keywords:

NP-complete problem; polynomial-time reduction; Max-SNP-hard problem; L-reduction; polynomial-time approximation scheme (PTAS) APPROXIMATION ALGORITHMS

DOI:

10.1134/S008154381309006X

Web of Science ID:

ISI:000327079000006

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	DEC
Publisher	MAIK NAUKA/INTERPERIODICA/SPRINGER
Address	233 SPRING ST, NEW YORK, NY 10013-1578 USA
Language	English
EISSN	1531-8605
Keywords-Plus	APPROXIMATION ALGORITHMS
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics, Applied; Mathematics
Author-Email	mkhachay@imm.uran.ru maschas\_briefen@mail.ru
ResearcherID-Numbers	Khachay, Michael/H-3251-2013
ORCID-Numbers	Khachay, Michael/0000-0003-3555-0080
Funding-Acknowledgement	Russian Foundation for Basic Research {[}10-01-00273, 10-07-00134]; Presidium of the Ural Branch of the Russian Academy of Sciences {[}12-P-1-1016, 12-S-1-1017/1]
Funding-Text	This work was supported by the Russian Foundation for Basic Research (project nos. 10-01-00273 and 10-07-00134) and by the Presidium of the Ural Branch of the Russian Academy of Sciences (project nos. 12-P-1-1016 and 12-S-1-1017/1).
Number-of-Cited-References	12
Usage-Count-Since-2013	2
Journal-ISO	Proc. Steklov Inst. Math.
Doc-Delivery-Number	253IT