|
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
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.
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
Linking options:
https://www.mathnet.ru/eng/umj25 https://www.mathnet.ru/eng/umj/v2/i2/p117
|
Statistics & downloads: |
Abstract page: | 257 | Full-text PDF : | 63 | References: | 53 |
|