zbMATH — the first resource for mathematics

Theoretical complexity of grid cover problems used in radar applications. (English) Zbl 1440.05058
Summary: Modern radars are highly flexible systems, relying on digital antennas to dynamically control the radar beam shape and position through electronic circuits. Radar surveillance is performed by sequential emission of different radar beams. Optimization of radar surveillance requires finding a minimal subset of radar beams, which covers and ensures detection over the surveillance space, among a collection of available radar beams with different shapes and positions, thus minimizing the required scanning time. Optimal radar surveillance can be modelled by grid covering, a specific geometric case of set covering where the universe set is laid out on a grid, representing the radar surveillance space, which must be covered using available subsets, representing the radar beams detection areas. While the set cover problem is generally difficult to solve optimally, certain geometric cases can be optimized in polynomial time. This paper studies the theoretical complexity of grid cover problems used for modelling radar surveillance, proving that unidimensional grids can be covered by strongly polynomial algorithms based on dynamic programming, whereas optimal covering of bidimensional grids is generally non-deterministic polynomially hard.

05B40 Combinatorial aspects of packing and covering
52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
90C39 Dynamic programming
90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Karp, Richard M., Reducibility among Combinatorial Problems, 85-103, (1972), Boston, MA
[2] Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, STOC, pp. 38-49. ACM, New York, NY, USA (1973). https://doi.org/10.1145/800125.804034
[3] Chvatal, V., A greedy heuristic for the set-covering problem, Math. Oper. Res., 4, 233-235, (1979) · Zbl 0443.90066
[4] Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. ACM, 41, 960-981, (1994) · Zbl 0814.68064
[5] Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC, pp. 475-484. ACM, New York, NY, USA (1997). https://doi.org/10.1145/258533.258641 · Zbl 0963.68175
[6] Escoffier, B.; Paschos, VT, Completeness in approximation classes beyond apx, Theor. Comput. Sci., 359, 369-377, (2006) · Zbl 1099.68135
[7] Srinivasan, A.: Improved approximations of packing and covering problems. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing, STOC, pp. 268-276. ACM, New York, NY, USA (1995). https://doi.org/10.1145/225058.225138 · Zbl 0920.90105
[8] Koch, T., MIPLIB 2010, Math. Progr. Comput., 3, 103, (2011)
[9] Pataki, Gábor; Tural, Mustafa; Wong, Erick B., Basis Reduction and the Complexity of Branch-and-Bound, 1254-1261, (2010), Philadelphia, PA · Zbl 1288.90131
[10] Li, Jian; Jin, Yifei, A PTAS for the Weighted Unit Disk Cover Problem, 898-909, (2015), Berlin, Heidelberg · Zbl 1440.68335
[11] Chan, TM; Grant, E., Exact algorithms and apx-hardness results for geometric packing and covering problems, Comput. Geom., 47, 112-124, (2014) · Zbl 1283.52032
[12] Schöbel, A.: Optimization in Public Transportation: Stop Location, Delay Management and Tariff Zone Design in a Public Transportation Network. Springer-Verlag New York, Inc., Secaucus (2006) · Zbl 1136.90002
[13] Hahn, PM; Gross, SD, Beam shape loss and surveillance optimization for pencil beam arrays, IEEE Trans. Aerosp. Electron. Syst., AES-5, 674-675, (1969)
[14] Torres, S., Adams, R., Curtis, C., Forren, E., Forsyth, D., Ivic, I., Priegnitz, D., Thompson, J., Warde, D.: A demonstration of adaptive weather surveillance and multifunction capabilities on the National Weather Radar Testbed Phased Array Radar. In: Radar Conference (Radar), 2014 International (2014). https://doi.org/10.1109/RADAR.2014.7060420
[15] Briheche, Y., Barbaresco, F., Bennis, F., Chablat, D., Gosselin, F.: Non-uniform constrained optimization of radar search patterns in direction cosines space using integer programming. In: 2016 17th International Radar Symposium (IRS) (2016). https://doi.org/10.1109/IRS.2016.7497343
[16] Barbaresco, F., Deltour, J., Desodt, G., Durand, B., Guenais, T., Labreuche, C.: Intelligent M3R radar time resources management: advanced cognition, agility & autonomy capabilities. In: Radar Conference—Surveillance for a Safer World, RADAR. International (2009)
[17] National Research Council: Evaluation of the Multifunction Phased Array Radar Planning Process. The National Academies Press, Washington, D.C. (2008). https://doi.org/10.17226/12438
[18] Stutzman, W., Thiele, G.: Antenna Theory and Design. Wiley, Hoboken (2012)
[19] Orfanidis, S.J.: Electromagnetic Waves and Antennas. Rutgers University, New Brunswick (2016). https://doi.org/10.1016/B978-075064947-6/50011-3
[20] Matouek, J., Gärtner, B.: Understanding and Using Linear Programming (Universitext). Springer-Verlag New York Inc., Secaucus (2006)
[21] Megiddo, N., On finding primal- and dual-optimal bases, ORSA J. Comput., 3, 63-65, (1991) · Zbl 0755.90056
[22] Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)
[23] Vazirani, V.V.: Approximation Algorithms. Springer-Verlag New York, Inc., Secaucus (2001). https://doi.org/10.1002/rsa.10038 · Zbl 0999.68546
[24] Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms, 1st edn. Cambridge University Press, New York (2011) · Zbl 1219.90004
[25] Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, 1st edn. Springer-Verlag New York Inc., Secaucus (1999) · Zbl 0937.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.