Ural Mathematical Journal
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Ural Math. J.:
Year:
Volume:
Issue:
Page:
Find






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


Ural Mathematical Journal, 2016, Volume 2, Issue 2, Pages 117–126
DOI: https://doi.org/10.15826/umj.2016.2.010
(Mi umj25)
 

This article is cited in 1 scientific paper (total in 1 paper)

On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line

Daniel M. Khachaiab, Michael Yu. Khachayab

a N.N. Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg, Russia
b Ural Federal University, Ekaterinburg, Russia
Full-text PDF (581 kB) Citations (1)
References:
Abstract: The Hitting Set Problem (HSP) is the well known extremal problem adopting research interest in the fields of combinatorial optimization, computational geometry, and statistical learning theory for decades. In the general setting, the problem is NP-hard and hardly approximable. Also, the HSP remains intractable even in very specific geometric settings, e.g. for axis-parallel rectangles intersecting a given straight line. Recently, for the special case of the problem, where all the rectangles are unit squares, a polynomial but very time consuming optimal algorithm was proposed. We improve this algorithm to decrease its complexity bound more than 100 degrees of magnitude. Also, we extend it to the more general case of the problem and show that the geometric HSP for axis-parallel (not necessarily unit) squares intersected by a line is polynomially solvable for any fixed range of squares to hit.
Keywords: Hitting set problem, Dynamic programming, Computational geometry, Parameterized complexity.
Funding agency Grant number
Russian Foundation for Basic Research 16-07-00266
Russian Academy of Sciences - Federal Agency for Scientific Organizations 15-7-1-23
This research was supported by Russian Foundation for Basic Research, grant no. 16-07-00266 and Complex Program of Ural Branch of RAS, grant no. 15-7-1-23.
Bibliographic databases:
Document Type: Article
Language: English
Citation: Daniel M. Khachai, Michael Yu. Khachay, “On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line”, Ural Math. J., 2:2 (2016), 117–126
Citation in format AMSBIB
\Bibitem{KhaKha16}
\by Daniel~M.~Khachai, Michael~Yu.~Khachay
\paper On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
\jour Ural Math. J.
\yr 2016
\vol 2
\issue 2
\pages 117--126
\mathnet{http://mi.mathnet.ru/umj25}
\crossref{https://doi.org/10.15826/umj.2016.2.010}
\zmath{https://zbmath.org/?q=an:1396.68127}
\elib{https://elibrary.ru/item.asp?id=27447891}
Linking options:
  • https://www.mathnet.ru/eng/umj25
  • https://www.mathnet.ru/eng/umj/v2/i2/p117
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Ural Mathematical Journal
    Statistics & downloads:
    Abstract page:257
    Full-text PDF :63
    References:53
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024