### ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INTERSECTING A STRAIGHT LINE

#### Abstract

#### Keywords

#### Full Text:

PDF#### References

Brönnimann H. and Goodrich M. T. Almost optimal set covers in finite vc-dimension // Discrete & Computational Geometry, 1995. Vol. 14, no. 4. P. 463–479. DOI: 10.1007/BF02570718

Chan T. M. Polynomial-time approximation schemes for packing and piercing fat objects // J. of Algorithms, 2003. Vol. 46, no. 2. P.178–189. DOI: 10.1016/S0196-6774(02)00294-8

Chepoi V. and Felsner S. Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve // Computational Geometry, 2013. Vol. 46, no. 9. P. 1036–1041. DOI: 10.1016/j.comgeo.2013.05.008

Correa J., Feuilloley L., Pérez-Lantero P. and Soto J. A. Independent and hitting sets of rectangles intersecting a diagonal line: Algorithms and complexity // Discrete & Computational Geometry, 2015. Vol. 53, no. 2. P. 344–365. DOI: 10.1007/s00454-014-9661-y

Fowler R. J., Paterson M. S. and. Tanimoto S. L. Optimal packing and covering in the plane are np-complete // Information Processing Letters, 1981. Vol. 12, no. 3. P. 133–137. DOI: 10.1016/0020-0190(81)90111-3

Haussler D. and Welzl E. Epsilon-nets and simplex range queries // Discrete & Computational Geometry, 1987. Vol. 2, no. 2. P. 127–151. DOI: 10.1007/BF02187876

Hochbaum D.and Maass W. Approximation schemes for covering and packing problems in image processing and vlsi // J. ACM, 1985. Vol. 32, no. 1. P. 130–136. DOI: 10.1145/2455.214106

Khachay M. Committee polyhedral separability: complexity and polynomial approximation // Machine Learning, 2015. Vol. 101, no 1. P. 231–251. DOI: 10.1007/s10994-015-5505-0

Khachay M. and Poberii M. Complexity and approximability of committee polyhedral separability of sets in general position // Informatica, 2009. Vol. 20, no. 2. P. 217–234.

Khachay M., Pobery M. and Khachay D. Integer partition problem: Theoretical approach to improving accuracy of classifier ensembles // International J. of Artificial Intelligence, 2015. Vol. 13, no. 1. P. 135–146.

Matoušek J. Lectures on Discrete Geometry. Springer: New York, 2002. DOI: 10.1007/978-1-4613-0039-7

Mudgal A. and 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), Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li, and Ding-Zhu Du (Ed.). LNCS, Springer International Publishing: Cham, 2015. Vol. 9486. P. 126–137. DOI: 10.1007/978-3-319-26626-8_10

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

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

Vapnik V. and Chervonenkis A. On the uniform convergence of relative frequencies of events to their probabilities // Theory Probab. Appl., 1971. Vol.16. P. 264–280. DOI: 10.1137/1116025

#### Article Metrics

### Refbacks

- There are currently no refbacks.