Geodesic
The computational complexity and approximability of a series of geometric covering problems
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 18 (2012) no. 3, pp. 247-260 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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). 
@article{TIMM_2012_18_3_a28,
     author = {M. Yu. Khachai and M. I. Poberii},
     title = {The computational complexity and approximability of a~series of geometric covering problems},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {247--260},
     year = {2012},
     volume = {18},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2012_18_3_a28/}
}
TY  - JOUR
AU  - M. Yu. Khachai
AU  - M. I. Poberii
TI  - The computational complexity and approximability of a series of geometric covering problems
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2012
SP  - 247
EP  - 260
VL  - 18
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2012_18_3_a28/
LA  - ru
ID  - TIMM_2012_18_3_a28
ER  - 
%0 Journal Article
%A M. Yu. Khachai
%A M. I. Poberii
%T The computational complexity and approximability of a series of geometric covering problems
%J Trudy Instituta matematiki i mehaniki
%D 2012
%P 247-260
%V 18
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2012_18_3_a28/
%G ru
%F TIMM_2012_18_3_a28
M. Yu. Khachai; M. I. Poberii. The computational complexity and approximability of a series of geometric covering problems. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 18 (2012) no. 3, pp. 247-260. http://geodesic.mathdoc.fr/item/TIMM_2012_18_3_a28/

[1] Agarwal P. K., Procopiuc C. M., “Exact and approximation algorithms for clustering”, Algorithmica, 33 (2002), 201–206 | DOI | MR

[2] Langerman S., Morin P., “Covering things with things”, Discrete Comput. Geom., 33 (2005), 717–729 | DOI | MR | Zbl

[3] Khachai M. Yu., “Voprosy vychislitelnoi slozhnosti protsedur obucheniya raspoznavaniyu v klasse komitetnykh kusochno-lineinykh reshayuschikh pravil”, Avtomatika i telemekhanika, 2010, no. 3, 178–189 | MR | Zbl

[4] Vazirany V., Approximation algorithms, Springer, Berlin, 2001, 378 pp. | MR

[5] Johnson D. S., “Approximation algorithms for combinatorial problems”, J. Comput. System Sci., 9:3 (1974), 256–278 | DOI | MR | Zbl

[6] Lovász L., “On the ratio of integer and fractional covers”, Discrete Math., 13 (1975), 383–390 | DOI | MR | Zbl

[7] Feige U., “A threshold of $\ln n$ for approximating set cover”, J. ACM, 45:4 (1998), 634–652 | DOI | MR | Zbl

[8] Megiddo N., Tamir A., “On the complexity of locating linear facilities in the plane”, Oper. Res. Let., 1:5 (1982), 194–197 | DOI | MR | Zbl

[9] Papadimitriou Ch., Yannakakis M., “Optimization, approximation, and complexity classes”, J. Comput. System Sci., 43:3 (1991), 425–440 | DOI | MR | Zbl

[10] Papadimitriou Ch., Computational complexity, Addison-Wesley, New York, 1995, 523 pp. | MR

[11] Poberii M. I., “O prinadlezhnosti klassu MAX-SNP-trudnykh zadach $\mathrm{MIN-PC}$ i $\mathrm{MASC-GP}(n)$”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16, no. 3, 2010, 210–216

[12] Schönhage A., Strassen V., “Schnelle Multiplikation großer Zahlen”, Computing, 7:3–4 (1971), 281–292 | DOI | MR