Geodesic
Computation of lower bounds on the network cost in location problems subject to distance constraints
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 46 (2006) no. 2, pp. 216-221 
G. G. Zabudskii. Computation of lower bounds on the network cost in location problems subject to distance constraints. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 46 (2006) no. 2, pp. 216-221. http://geodesic.mathdoc.fr/item/ZVMMF_2006_46_2_a2/
@article{ZVMMF_2006_46_2_a2,
     author = {G. G. Zabudskii},
     title = {Computation of lower bounds on the network cost in location problems subject to distance constraints},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {216--221},
     year = {2006},
     volume = {46},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2006_46_2_a2/}
}
TY  - JOUR
AU  - G. G. Zabudskii
TI  - Computation of lower bounds on the network cost in location problems subject to distance constraints
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2006
SP  - 216
EP  - 221
VL  - 46
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2006_46_2_a2/
LA  - ru
ID  - ZVMMF_2006_46_2_a2
ER  - 
%0 Journal Article
%A G. G. Zabudskii
%T Computation of lower bounds on the network cost in location problems subject to distance constraints
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2006
%P 216-221
%V 46
%N 2
%U http://geodesic.mathdoc.fr/item/ZVMMF_2006_46_2_a2/
%G ru
%F ZVMMF_2006_46_2_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

Methods for the computation of lower bounds on the cost of the connecting network for the continuous and discrete variants of the problem of location of interconnected objects subject to minimal or maximal distances between them are proposed. For the continuous variant, the bound is found by solving a linear programming problem. For the discrete variant, an assignment problem with a rectangular matrix containing forbidden entries is constructed. An application of the assignment problem for locating objects of various sizes is described.

[1] Zabudskii G. G., “O tselochislennoi postanovke odnoi zadachi razmescheniya ob'ektov na linii”, Upravlyaemye sistemy, 30, Novosibirsk, 1990, 35–45 | MR

[2] Burcard R. E., Stratmamm K., “Numerical investigations on quadratic assignment problems”, Naval. Res. Logist. Quadratic Quart., 25:1 (1978), 129–148 | DOI

[3] Sachkov V. H., Vvedenie v kombinatornye metody diskretnoi matematiki, Nauka, M., 1982 | MR | Zbl

[4] Rubinshtein M. M., “Ob algoritmakh resheniya zadachi o naznachenii”, Avtomatika i telemekhan., 1981, no. 7, 145–154 | MR