Geodesic
On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
Ural mathematical journal, Tome 2 (2016) no. 2, pp. 117-126

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{UMJ_2016_2_2_a9,
     author = {Daniel M. Khachai and Michael Yu. Khachay},
     title = {On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line},
     journal = {Ural mathematical journal},
     pages = {117--126},
     publisher = {mathdoc},
     volume = {2},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2016_2_2_a9/}
}
TY  - JOUR
AU  - Daniel M. Khachai
AU  - Michael Yu. Khachay
TI  - On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
JO  - Ural mathematical journal
PY  - 2016
SP  - 117
EP  - 126
VL  - 2
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UMJ_2016_2_2_a9/
LA  - en
ID  - UMJ_2016_2_2_a9
ER  - 
%0 Journal Article
%A Daniel M. Khachai
%A Michael Yu. Khachay
%T On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line
%J Ural mathematical journal
%D 2016
%P 117-126
%V 2
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UMJ_2016_2_2_a9/
%G en
%F UMJ_2016_2_2_a9
Daniel M. Khachai; Michael Yu. Khachay. On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line. Ural mathematical journal, Tome 2 (2016) no. 2, pp. 117-126. http://geodesic.mathdoc.fr/item/UMJ_2016_2_2_a9/