Geodesic
Optimization of a multiple covering of a bounded set with circles
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 4, pp. 757-769 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Numerical algorithms for the optimization of multiple covering of a bounded set $G$ in the plane $P$ with equal circles are proposed. The variants in which $G$ is a connected bounded set in $P$ or a finite set in $P$ are considered. The circles may be centered at arbitrary points of $G$ or at points belonging to a given set. Minimization of the radius of the given number of circles and minimization of the number of circles of a given radius are considered. Models and solution algorithms are described, and estimates of the solutions provided by most variants are given. Numerical results are presented. 
@article{ZVMMF_2010_50_4_a12,
     author = {Sh. I. Galiev and M. A. Karpova},
     title = {Optimization of a multiple covering of a bounded set with circles},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {757--769},
     year = {2010},
     volume = {50},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_4_a12/}
}
TY  - JOUR
AU  - Sh. I. Galiev
AU  - M. A. Karpova
TI  - Optimization of a multiple covering of a bounded set with circles
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 757
EP  - 769
VL  - 50
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_4_a12/
LA  - ru
ID  - ZVMMF_2010_50_4_a12
ER  - 
%0 Journal Article
%A Sh. I. Galiev
%A M. A. Karpova
%T Optimization of a multiple covering of a bounded set with circles
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 757-769
%V 50
%N 4
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_4_a12/
%G ru
%F ZVMMF_2010_50_4_a12
Sh. I. Galiev; M. A. Karpova. Optimization of a multiple covering of a bounded set with circles. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 4, pp. 757-769. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_4_a12/

[1] Feiesh Tot L., Raspolozheniya na ploskosti, na sfere i v prostranstve, Fizmatgiz, M., 1958

[2] Fejes Tot G., “Multiple packing and covering of spheres”, Acta Math. Acad. Sci. Hungar., 34:1–2 (1979), 165–176 | MR | Zbl

[3] Konvei Dzh., Sloen N., Upakovki sharov, reshetki i gruppy, v. 1, 2, Mir, M., 1990

[4] Piyavskii S. A., “Ob optimizatsii setei”, Izv. AN SSSR. Tekhn. kibernetika, 1968, no. 1, 68–80

[5] Brusov V. S., Piyavskii S. A., “Vychislitelnyi algoritm optimalnogo pokrytiya oblastei ploskosti”, Zh. vychisl. matem. i matem. fiz., 11:2 (1971), 304–312

[6] Tarnai T., Gáspár Zs., “Covering a square by equal circles”, Elem. Math., 50 (1995), 167–170 | MR | Zbl

[7] Melissen J. B. M., Schuur P. C., “Improved coverings of a square with six and eight equal circles”, Electron. J. Combin., 3, R32, 10 pp. (electronic) | MR | Zbl

[8] Heppes A., Melissen H., “Covering a rectangle with equal circles”, Period. Math. Hungar., 34 (1997), 65–81 | DOI | MR | Zbl

[9] Melissen H., “Loosest circle coverings of an equilateral triangle”, Math. Mag., 70 (1997), 119–125 | DOI | MR

[10] Heppes A., Melissen H., “Covering a rectangle with equal circles”, Period. Math. Hungar., 34 (1997), 65–81 | DOI | MR | Zbl

[11] Melissen J. B. M., Schuur P. C., “Covering a rectangle with six and seven circles”, Discrete Appl. Math., 99 (2000), 149–156 | DOI | MR | Zbl

[12] Nurmela K. J., “Conjectually optimal covering of an equilateral triangle with up to 36 equal circles”, Experiment. Math., 9:2 (2000) | MR | Zbl

[13] Nurmela K. J., Östergard P. R. J., Covering a square with up to 30 equal circles, Res. rept A62. Lab. Technol. Helsinki Univ., 2000 http://www.tcs.hut.fi/Publications/reports | Zbl

[14] Zahn C. T., “Black box maximization of circular coverage”, J. Res. Nat. Bur. Standards, Sect. B, 66 (1962), 181–216 | MR | Zbl

[15] Jandl H., Wieder K., “A continuous set covering problem as a quasidifferentiable optimization problem”, Optimizat. J. Math. Program. and Operat. Res., 19:6 (1988), 781–802 | MR | Zbl

[16] Drezner Z., “The $p$-centre problem — heuristic and optimal algorithms”, J. OR Soc., 35 (1984), 741–748 | Zbl

[17] Galiev Sh. I., “Napravleniya ubyvaniya dlya minimaksiminnykh zadach”, Zh. vychisl. matem. i matem. fiz., 34:3 (1994), 323–343 | MR | Zbl

[18] Zhuravlev Yu. I., Izbrannye trudy, Magistr, M., 1998

[19] Sigal I. Kh., Ivanova A. P., Vvedenie v prikladnoe diskretnoe programmirovanie: Modeli i vychislitelnye algoritmy, Fizmatlit, M., 2002

[20] Kovalev M. M., Diskretnaya optimizatsiya (tselochislennoe programmirovanie), Izd. 2-e, stereotipnoe, Editorial URSS, M., 2003

[21] Leontev V. K., “Diskretnaya optimizatsiya”, Zh. vychisl. matem. i matem. fiz., 47:2 (2007), 338–352 | MR

[22] Chvatal V., “A greedy heuristic for the set covering”, Math. Optimizat. Res., 4 (1979), 233–235 | DOI | MR | Zbl

[23] Johnson D., “Approximation algorithms for combinatorial problems”, J. Comput. and System Sci., 9 (1974), 256–248 | DOI | MR

[24] Hall N., Hochbaum D., “A fast approximation algorithm for the multicovering problem”, Discrete Appl. Math., 15 (1989), 35–40 | DOI | MR

[25] Ceria S., Nobili P., Sassano A., “A Lagrangian-based heuristic for large-scale set covering problems”, Math. Program., 81:2 (1998), 215–228 | DOI | MR | Zbl

[26] Bertsimas D., Vohra R., “Rounding algorithms for covering problems”, Math. Program., 80 (1998), 63–89 | MR | Zbl

[27] Fujito T., “On combinatorial approximation of covering $0-1$ integer programs and partial set cover”, J. Combinatorial Optimizat., 8 (2004), 439–452 | DOI | MR | Zbl

[28] Galiev Sh. I., “Mnogokratnye upakovki i pokrytiya sfery”, Diskretnaya matem., 8:3 (1996), 148–160 | MR | Zbl

[29] Galiev Sh. I., Zabotin V. I., “O nepreryvnom obzore poverkhnosti Zemli”, Issl. Zemli iz kosmosa, 1983, no. 1, 117–120 | MR

[30] Fejes Tot G., “Multiple packing and covering of the plane with circles”, Acta Math. Acad. Sci. Hungar., 27:1–2 (1976), 135–140 | DOI | MR | Zbl

[31] Belacel N., Hansen P., Mladenovic N., “Fuzzy $J$-means: A new heuristic for fuzzy clustering”, Pattern Recognition, 35 (2002), 2193–2200 | DOI | Zbl

[32] Demyanov V. F., Malozemov V. N., Vvedenie v minimaks, Nauka, M., 1972 | MR

[33] http://www-fp.mcs.anl.gov/otc/Tools/PCx/

[34] http://tech.groups.yahoo.com/group/lp_solve/