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

Daniel M. Khachai   ; Michael Yu. Khachay

Ural mathematical journal, Tome 2 (2016) no. 2, pp. 117-126

Résumé

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.

Détail

Keywords: Hitting set problem, Dynamic programming, Computational geometry, Parameterized complexity.

Bibliographie

[1] Brönnimann H., Goodrich M.T., “Almost optimal set covers in finite vc-dimension”, Discrete Computational Geometry, 14:4 (1995), 463–479 | DOI

[2] Chan T.M., “Polynomial-time approximation schemes for packing and piercing fat objects”, J. of Algorithms, 46:2 (2003), 178-189. | DOI

[3] Chepoi V., Felsner S., “Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve”, Computational Geometry, 46:9 (2013), 1036–1041 | DOI

[4] Correa J., Feuilloley L., Pérez-Lantero P., Soto J.A., “Independent and hitting sets of rectangles intersecting a diagonal line. Algorithms and complexity.”, Discrete Computational Geometry, 53:2 (2015), 344–365, arXiv: 1309.6659v2 | DOI

[5] Fowler R.J., Paterson M.S., Tanimoto S.L., “Optimal packing and covering in the plane are np-complete”, Information Processing Letters, 12:3 (1981), 133–137 | DOI

[6] Haussler D., Welzl E., “Epsilon-nets and simplex range queries”, Discrete Computational Geometry, 2:2 (1987), 127–151 | DOI

[7] Hochbaum D., Maass W., “Approximation schemes for covering and packing problems in image processing and VLSI”, J. ACM, 32:1 (1985), 130–136 | DOI

[8] Khachay M., “Committee polyhedral separability: complexity and polynomial approximation”, Machine Learning, 101:1 (2015), 231–251 | DOI

[9] Khachay M., Poberii M., “Complexity and approximability of committee polyhedral separability of sets in general position”, Informatica, 20:2 (2009), 217–234

[10] Khachay M., Pobery M., Khachay D., “Integer partition problem: Theoretical approach to improving accuracy of classifier ensembles”, Int. J. of Artificial Intelligence, 13:1 (2015), 135–146

[11] Matoušek J., Lectures on Discrete Geometry, Springer, New York, 2002 | DOI

[12] Mudgal A., Pandit S., “Covering, hitting, piercing and packing rectangles intersecting an inclined line”, Proceedings of the Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, v. 9486, eds. Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, and Ding-Zhu Du, 2015, 126–137

[13] Ramakrishnan S. and Emary I.M.M.El., Wireless sensor networks: from theory to applications, CRCPress, Taylor Francis, 2014

[14] Schapire R. and Freund Y., Boosting: Foundations and algorithms, MIT Press, 2012

[15] Vapnik V. and Chervonenkis A., “On the uniform convergence of relative frequencies of events to their probabilities”, Theory Probab. Appl., 16 (1971), 264–280 | DOI