Trudy Instituta Matematiki i Mekhaniki UrO RAN
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Trudy Inst. Mat. i Mekh. UrO RAN:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2012, Volume 18, Number 3, Pages 247–260 (Mi timm859)  
This article is cited in 3 scientific papers (total in 3 papers)

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

M. Yu. Khachaiab, M. I. Poberiib

a Ural Federal University
b Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences
Full-text PDF (211 kB) Citations (3)
References:
PDF
HTML
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).
Received: 26.03.2012
English version:
Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2013, Volume 283, Issue 1, Pages 64–77
DOI: https://doi.org/10.1134/S008154381309006X
Bibliographic databases:
Document Type: Article
UDC: 519.6
Language: Russian
Citation: 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, 18, no. 3, 2012, 247–260; Proc. Steklov Inst. Math. (Suppl.), 283, suppl. 1 (2013), 64–77
Citation in format AMSBIB
\Bibitem{KhaPob12}
\by M.~Yu.~Khachai, M.~I.~Poberii
\paper The computational complexity and approximability of a~series of geometric covering problems
\serial Trudy Inst. Mat. i Mekh. UrO RAN
\yr 2012
\vol 18
\issue 3
\pages 247--260
\mathnet{http://mi.mathnet.ru/timm859}
\elib{https://elibrary.ru/item.asp?id=17937031}
\transl
\jour Proc. Steklov Inst. Math. (Suppl.)
\yr 2013
\vol 283
\issue , suppl. 1
\pages 64--77
\crossref{https://doi.org/10.1134/S008154381309006X}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000327079000006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84887604494}
Linking options:
  • https://www.mathnet.ru/eng/timm859
  • https://www.mathnet.ru/eng/timm/v18/i3/p247
    • This publication is cited in the following 3 articles:
    1. Khorkov V A., Galiev I Sh., “Optimization of a K-Covering of a Bounded Set With Circles of Two Given Radii”, Open Comput. Sci., 11:1 (2021), 232–240  crossref  isi  scopus
    2. Sh. I. Galiev, A. V. Khorkov, “On the number and arrangement of sensors for the multiple covering of bounded plane domains”, J. Appl. Industr. Math., 13:1 (2019), 43–53  mathnet  crossref  crossref  elib
    3. Sh. I. Galiev, A. V. Khorkov, “Mnogokratnye pokrytiya krugami ravnostoronnego treugolnika, kvadrata i kruga”, Diskretn. analiz i issled. oper., 22:6 (2015), 5–28  mathnet  crossref  mathscinet  elib
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Trudy Instituta Matematiki i Mekhaniki UrO RAN
    Statistics & downloads:
    Abstract page:348
    Full-text PDF :103
    References:78
    First page:1
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025