Approximate solution of the $p$-median minimization problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 9, pp. 1614-1621
Voir la notice de l'article provenant de la source Math-Net.Ru
A version of the facility location problem (the well-known $p$-median minimization problem) and its generalization — the problem of minimizing a supermodular set function — is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the $p$-median minimization problem in terms of the production and transportation cost matrix is obtained.
@article{ZVMMF_2016_56_9_a6,
author = {V. P. Il'ev and S. D. Il'eva and A. A. Navrotskaya},
title = {Approximate solution of the $p$-median minimization problem},
journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
pages = {1614--1621},
publisher = {mathdoc},
volume = {56},
number = {9},
year = {2016},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_9_a6/}
}
TY - JOUR AU - V. P. Il'ev AU - S. D. Il'eva AU - A. A. Navrotskaya TI - Approximate solution of the $p$-median minimization problem JO - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki PY - 2016 SP - 1614 EP - 1621 VL - 56 IS - 9 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_9_a6/ LA - ru ID - ZVMMF_2016_56_9_a6 ER -
%0 Journal Article %A V. P. Il'ev %A S. D. Il'eva %A A. A. Navrotskaya %T Approximate solution of the $p$-median minimization problem %J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki %D 2016 %P 1614-1621 %V 56 %N 9 %I mathdoc %U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_9_a6/ %G ru %F ZVMMF_2016_56_9_a6
V. P. Il'ev; S. D. Il'eva; A. A. Navrotskaya. Approximate solution of the $p$-median minimization problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 9, pp. 1614-1621. http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_9_a6/