{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T15:14:46Z","timestamp":1774365286411,"version":"3.50.1"},"reference-count":36,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>A numerical method for investigating <jats:italic>k<\/jats:italic>-coverings of a convex bounded set with circles of two given radii is proposed. Cases with constraints on the distances between the covering circle centers are considered. An algorithm for finding an approximate number of such circles and the arrangement of their centers is described. For certain specific cases, approximate lower bounds of the density of the <jats:italic>k<\/jats:italic>-covering of the given domain are found. We use either 0\u20131 linear programming or general integer linear programming models. Numerical results demonstrating the effectiveness of the proposed methods are presented.<\/jats:p>","DOI":"10.1515\/comp-2020-0219","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T23:10:02Z","timestamp":1614035402000},"page":"232-240","source":"Crossref","is-referenced-by-count":3,"title":["Optimization of a k-covering of a bounded set with circles of two given radii"],"prefix":"10.1515","volume":"11","author":[{"given":"Alexander V.","family":"Khorkov","sequence":"first","affiliation":[{"name":"Kazan National Research Technical University named after A.N. Tupolev-KAI"}]},{"given":"Shamil I.","family":"Galiev","sequence":"additional","affiliation":[{"name":"Kazan National Research Technical University named after A.N. Tupolev-KAI"}]}],"member":"374","published-online":{"date-parts":[[2021,1,29]]},"reference":[{"key":"2022020121510261788_j_comp-2020-0219_ref_001","doi-asserted-by":"crossref","unstructured":"Brusov V.S., Piyavskii S.A., A computational algorithm for the optimal covering of planar domains, USSR Computational Mathematics and Mathematical Physics, 1971, 11(2), 17\u201327","DOI":"10.1016\/0041-5553(71)90161-3"},{"key":"2022020121510261788_j_comp-2020-0219_ref_002","doi-asserted-by":"crossref","unstructured":"Drezner Z., Facility location: A survey of applications and methods, Springer-Verlag, New York, 1995","DOI":"10.1007\/978-1-4612-5355-6"},{"key":"2022020121510261788_j_comp-2020-0219_ref_003","doi-asserted-by":"crossref","unstructured":"Drezner Z., Hamacher H.W., Facility location: Applications and theory, Springer-Verlag, Berlin, Germany, 2002","DOI":"10.1007\/978-3-642-56082-8"},{"key":"2022020121510261788_j_comp-2020-0219_ref_004","doi-asserted-by":"crossref","unstructured":"ReVelle C.S., Eiselt H.A., Location analysis: A synthesis and survey, European Journal of Operational Research, 2005, 165, 1\u201319","DOI":"10.1016\/j.ejor.2003.11.032"},{"key":"2022020121510261788_j_comp-2020-0219_ref_005","doi-asserted-by":"crossref","unstructured":"Zanjirani Farahani R., Hekmatfar M., Facility Location: Concepts, Models, Algorithms and Case Studies, Physica-Verlag Heidelberg, 2009","DOI":"10.1007\/978-3-7908-2151-2"},{"key":"2022020121510261788_j_comp-2020-0219_ref_006","doi-asserted-by":"crossref","unstructured":"Berman O., Drezner Z., Krass D., Wesolowsky G.O., The variable radius covering problem, European Journal of Operational Research, 2009, 196, 516\u2013525","DOI":"10.1016\/j.ejor.2008.03.046"},{"key":"2022020121510261788_j_comp-2020-0219_ref_007","doi-asserted-by":"crossref","unstructured":"Ammari Y.M., Challenges and Opportunities of Connected k-Covered Wireless Sensor Networks, Springer, Berlin, 2009","DOI":"10.1007\/978-3-642-01878-7"},{"key":"2022020121510261788_j_comp-2020-0219_ref_008","unstructured":"Huang C.F., Tseng Y.C., A Survey of Solutions to the Coverage Problems in Wireless Sensor Networks, Journal of Internet Technology, 2005, 6(1), 1\u20138"},{"key":"2022020121510261788_j_comp-2020-0219_ref_009","doi-asserted-by":"crossref","unstructured":"Wang B., Coverage Problems in Sensor Networks: A Survey, ACM Computing Surveys, 2011, 43(4), 167\u2013170, DOI: 10.1145\/1978802.1978811","DOI":"10.1145\/1978802.1978811"},{"key":"2022020121510261788_j_comp-2020-0219_ref_010","doi-asserted-by":"crossref","unstructured":"Yeasmin N., k-Coverage Problems and Solutions in Wireless Sensor Networks: A Survey, International Journal of Computer Applications, 2014, 100(17), 1\u20136, DOI: 10.5120\/17614-8309","DOI":"10.5120\/17614-8309"},{"key":"2022020121510261788_j_comp-2020-0219_ref_011","unstructured":"Astrakov S.N., Erzin A.I., Zalyubovskii V.V., Sensor networks and planar region coverage with circles, Discrete analysis and operation study, 2009, 16(3), 3\u201319"},{"key":"2022020121510261788_j_comp-2020-0219_ref_012","doi-asserted-by":"crossref","unstructured":"Kumar S., Lai T.H., Balogh J., On k-coverage in a mostly sleeping sensor network, In Proceedings of the 10th Annual International Conference on Mobile Computing and Networking \u2014 MobiCom\u201904, 2004, 144\u2013158, DOI: 10.1145\/1023720.1023735","DOI":"10.1145\/1023720.1023735"},{"key":"2022020121510261788_j_comp-2020-0219_ref_013","doi-asserted-by":"crossref","unstructured":"Nurmella K.J., Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles, Experimental Mathematics, 2000, 9(2), 241\u2013250, DOI: 10.1080\/10586458.2000.10504649","DOI":"10.1080\/10586458.2000.10504649"},{"key":"2022020121510261788_j_comp-2020-0219_ref_014","unstructured":"Nurmella K.J., Covering a circle by congruent circular discs (preprint), Departament of Computer Sciences and Engineering, Helsinki University of Technology, 1998"},{"key":"2022020121510261788_j_comp-2020-0219_ref_015","unstructured":"Nurmella K.J., \u00d6stergard, P.R.J.: Covering a square with up to 30 equal circles. In.: Research report A62 Laboratory for Technology Helsinki University, 2000"},{"key":"2022020121510261788_j_comp-2020-0219_ref_016","doi-asserted-by":"crossref","unstructured":"Suzuki A., Drezner, Z. The minimum number equitable radius location problems with continuous demand, European Journal of Operational Research, 2009, 195, 17\u201330, DOI: 10.1016\/j.ejor.2008.01.022","DOI":"10.1016\/j.ejor.2008.01.022"},{"key":"2022020121510261788_j_comp-2020-0219_ref_017","doi-asserted-by":"crossref","unstructured":"Erzin A., Astrakov S., Min-Density Stripe Covering and Applications in Sensor Network, In: Murgante B., Gervasi O., Iglesias A., Taniar D., Apduhan B.O. (eds.) ICCSA 2011. LNCS, Springer Heidelberg, 2011, 6784, 152\u2013162, DOI: 10.1007\/978-3-642-21931-3_13","DOI":"10.1007\/978-3-642-21931-3_13"},{"key":"2022020121510261788_j_comp-2020-0219_ref_018","unstructured":"Astrakov S.N., Erzin A.I., Construction of efficient covering models in the monitoring of extended objects, Vychisl. Tekhnol., 2012, 17(1), 26\u201334"},{"key":"2022020121510261788_j_comp-2020-0219_ref_019","doi-asserted-by":"crossref","unstructured":"Erzin A.I., Shabelnikova N.A., About density of a covering of a strip with identical sectors, J. Appl. Industr. Math., 2015, 9(4), 461\u2013468","DOI":"10.1134\/S199047891504002X"},{"key":"2022020121510261788_j_comp-2020-0219_ref_020","doi-asserted-by":"crossref","unstructured":"Fejes T\u00f3th, G., Multiple packing and covering of the plane with circles. Acta Mathematica Academiae Scientiarum Hungarica, 1976, 27(1\u20132), 135\u2013140","DOI":"10.1007\/BF01896768"},{"key":"2022020121510261788_j_comp-2020-0219_ref_021","unstructured":"Galiev Sh.I., Khorkov A.V., Multiple circle coverings of an equilateral triangle, square, and circle. Diskretn. Analiz Issl. Oper., 2015, 22(6), 5\u201328, DOI: 10.17377\/daio.2015.22.482"},{"key":"2022020121510261788_j_comp-2020-0219_ref_022","doi-asserted-by":"crossref","unstructured":"Chakrabarty K., Iyengar S.S, Qi H., Cho E., Grid coverage for surveillance and target location in distributed sensor networks, IEEE Transactions on Computers, 2002, 51(12), 1448\u20131458","DOI":"10.1109\/TC.2002.1146711"},{"key":"2022020121510261788_j_comp-2020-0219_ref_023","doi-asserted-by":"crossref","unstructured":"Fejes T\u00f3th, G., Covering the plane with two kinds of circles, Discrete and Computational Geometry, 1995, 13(3\u20134), 445\u2013457, DOI: 10.1007\/BF02574055","DOI":"10.1007\/BF02574055"},{"key":"2022020121510261788_j_comp-2020-0219_ref_024","doi-asserted-by":"crossref","unstructured":"Galiev Sh.I., Karpova M.A., Optimization of Multiple Covering of a Bounded Set with Circles, Computational Mathematics and Mathematical Physics, 2010, 50, 721\u2013732","DOI":"10.1134\/S0965542510040135"},{"key":"2022020121510261788_j_comp-2020-0219_ref_025","doi-asserted-by":"crossref","unstructured":"Galiev Sh.I., Lisafina M.S., Linear models for the approximate solution of the problem of packing equal circles into a given domain, European Journal of Operational Research, 2013, 230, 505\u2013514","DOI":"10.1016\/j.ejor.2013.04.050"},{"key":"2022020121510261788_j_comp-2020-0219_ref_026","doi-asserted-by":"crossref","unstructured":"Galiev Sh.I., Khorkov A.V., Optimization of the Number and Arrangement of Circles of Two Radii for Forming a k-Covering of a Bounded Set, Computational Mathematics and Mathematical Physics, 2019, 59(4), 676\u2013687","DOI":"10.1134\/S0965542519040031"},{"key":"2022020121510261788_j_comp-2020-0219_ref_027","doi-asserted-by":"crossref","unstructured":"Galiev Sh.I., Khorkov A.V., On the Number and Arrangement of Sensors for Multiple Covering of Bounded Plane Domains, Journal of Applied and Industrial Mathematics, 2019, 13(1), 43\u201353","DOI":"10.1134\/S199047891901006X"},{"key":"2022020121510261788_j_comp-2020-0219_ref_028","unstructured":"Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Co. New York, NY, USA, 1979"},{"key":"2022020121510261788_j_comp-2020-0219_ref_029","doi-asserted-by":"crossref","unstructured":"Megiddo N., Supowit K., On the complexity of some common geometric location problems, SIAM Journal on Computing, 1984, 13(1), 182\u2013196 10.1137\/0213014","DOI":"10.1137\/0213014"},{"key":"2022020121510261788_j_comp-2020-0219_ref_030","doi-asserted-by":"crossref","unstructured":"Culberson J.C., Reckhow R.A., Covering polygons is hard. J. Algorithms, 1994, 17, 2\u201344","DOI":"10.1006\/jagm.1994.1025"},{"key":"2022020121510261788_j_comp-2020-0219_ref_031","unstructured":"Kuzyurin, N.N., On the complexity of asymptotically optimal coverings and packings, Doklady Mathematics, 1998, 58(3), 345\u2013346"},{"key":"2022020121510261788_j_comp-2020-0219_ref_032","unstructured":"Eremeev A.V., Zaozerskaya L.A., Kolokolov A.A., Set covering problem: Complexity, algorithms, and experimental studies, Diskretn. Analiz Issl. Oper., 2009, 7(2), 22\u201346"},{"key":"2022020121510261788_j_comp-2020-0219_ref_033","unstructured":"Khachai M.Yu., Poberii M.I., The computational complexity and approximability of a series of geometric covering problems, Trudy Inst. Mat. i Mekh. UrO RAN, 2012, 18(3), 247\u2013260"},{"key":"2022020121510261788_j_comp-2020-0219_ref_034","unstructured":"Astrakov S.N., Coverings of Sets with Restrictions on the Arrangement of Circles, In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of the OPTIMA\u20132017 Conference, Petrovac, Montenegro, 2017, 67\u201372"},{"key":"2022020121510261788_j_comp-2020-0219_ref_035","doi-asserted-by":"crossref","unstructured":"Do\u011fan\u00e7ay K., Hmam H., Optimal Angular Sensor Separation for AOA Localization, Signal Process, 2008, 88(5), 1248\u20131260","DOI":"10.1016\/j.sigpro.2007.11.013"},{"key":"2022020121510261788_j_comp-2020-0219_ref_036","doi-asserted-by":"crossref","unstructured":"Kim J.E., Yoon M.K., Han J., Lee C.G., Sensor Placement for 3-Coverage with Minimum Separation Requirements, Distributed Computing in Sensor Systems: 4th IEEE International Conference, 2008, 5067, 266\u2013281, DOI: 10.1007\/978-3-540-69170-9_18","DOI":"10.1007\/978-3-540-69170-9_18"}],"container-title":["Open Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2020-0219\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2020-0219\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T22:20:52Z","timestamp":1643754052000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2020-0219\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,1]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1,13]]},"published-print":{"date-parts":[[2021,1,1]]}},"alternative-id":["10.1515\/comp-2020-0219"],"URL":"https:\/\/doi.org\/10.1515\/comp-2020-0219","relation":{},"ISSN":["2299-1093"],"issn-type":[{"value":"2299-1093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,1]]}}}