ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin.
2016-12-01
|
| Series: | Ural Mathematical Journal |
| Subjects: | |
| Online Access: | https://umjuran.ru/index.php/umj/article/view/64 |
| _version_ | 1818759379115048960 |
|---|---|
| author | Daniel M. Khachay Michael Yu. Khachay |
| author_facet | Daniel M. Khachay Michael Yu. Khachay |
| author_sort | Daniel M. Khachay |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-18T06:41:47Z |
| format | Article |
| id | doaj.art-aadeffac36c3414682a637b1a0e29f1b |
| institution | Directory Open Access Journal |
| issn | 2414-3952 |
| language | English |
| last_indexed | 2024-12-18T06:41:47Z |
| publishDate | 2016-12-01 |
| publisher | Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin. |
| record_format | Article |
| series | Ural Mathematical Journal |
| spelling | doaj.art-aadeffac36c3414682a637b1a0e29f1b2022-12-21T21:17:36ZengKrasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin.Ural Mathematical Journal2414-39522016-12-012210.15826/umj.2016.2.01027ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINEDaniel M. Khachay0Michael Yu. Khachay1Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences; Ural Federal University, EkaterinburgKrasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences; Ural Federal University, EkaterinburgThe 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.https://umjuran.ru/index.php/umj/article/view/64Hitting set problem, Dynamic programming, Computational geometry, Parameterized complexity. |
| spellingShingle | Daniel M. Khachay Michael Yu. Khachay ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE Ural Mathematical Journal Hitting set problem, Dynamic programming, Computational geometry, Parameterized complexity. |
| title | ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE |
| title_full | ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE |
| title_fullStr | ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE |
| title_full_unstemmed | ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE |
| title_short | ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE |
| title_sort | on parameterized complexity of hitting set problem for axis parallel squares intersecting a straight line |
| topic | Hitting set problem, Dynamic programming, Computational geometry, Parameterized complexity. |
| url | https://umjuran.ru/index.php/umj/article/view/64 |
| work_keys_str_mv | AT danielmkhachay onparameterizedcomplexityofhittingsetproblemforaxisparallelsquaresintersectingastraightline AT michaelyukhachay onparameterizedcomplexityofhittingsetproblemforaxisparallelsquaresintersectingastraightline |