On parameterized complexity of the hitting set problem for axis-parallel squares intersecting a straight line. (English) Zbl 1396.68127

Khachai, Daniel M.; Khachay, Michael Yu.

Ural Math. J. 2, No. 2, 117-126 (2016).

Summary: 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.

MSC:

68U05	Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25	Analysis of algorithms and problem complexity
68W40	Analysis of algorithms

Keywords:

hitting set problem; dynamic programming; computational geometry; parameterized complexity

Software:

AdaBoost.MH

References:

[1]	[1] Brönnimann H., Goodrich M.T., “Almost optimal set covers in finite vc-dimension”, Discrete & Computational Geometry, 14:4 (1995), 463-479 · Zbl 0841.68122
[2]	[2] Chan T.M., “Polynomial-time approximation schemes for packing and piercing fat objects”, J. of Algorithms, 46:2 (2003), 178-189. · Zbl 1030.68093
[3]	[3] Chepoi V., Felsner S., “Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve”, Computational Geometry, 46:9 (2013), 1036-1041 · Zbl 1270.05028
[4]	[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 · Zbl 1315.52020
[5]	[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 · Zbl 0469.68053
[6]	[6] Haussler D., Welzl E., “Epsilon-nets and simplex range queries”, Discrete & Computational Geometry, 2:2 (1987), 127-151 · Zbl 0619.68056
[7]	[7] Hochbaum D., Maass W., “Approximation schemes for covering and packing problems in image processing and VLSI”, J. ACM, 32:1 (1985), 130-136 · Zbl 0633.68027
[8]	[8] Khachay M., “Committee polyhedral separability: complexity and polynomial approximation”, Machine Learning, 101:1 (2015), 231-251 · Zbl 1343.68198
[9]	[9] Khachay M., Poberii M., “Complexity and approximability of committee polyhedral separability of sets in general position”, Informatica, 20:2 (2009), 217-234 · Zbl 1194.68261
[10]	[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]	[11] Matoušek J., Lectures on Discrete Geometry, Springer, New York, 2002
[12]	[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 · Zbl 1478.90112
[13]	[13] Ramakrishnan S. and Emary I.M.M.El., Wireless sensor networks: from theory to applications, CRCPress, Taylor & Francis, 2014
[14]	[14] Schapire R. and Freund Y., Boosting: Foundations and algorithms, MIT Press, 2012 · Zbl 1278.68021
[15]	[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 · Zbl 0247.60005