Geodesic
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 
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/
@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},
     year = {2016},
     volume = {56},
     number = {9},
     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
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
%U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_9_a6/
%G ru
%F ZVMMF_2016_56_9_a6

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.

[1] Kariv O., Hakimi S. L., “An algorithmic approach to network location problems. II. The $p$-medians”, SIAM J. Appl. Math., 37:3 (1979), 539–560 | DOI | MR | Zbl

[2] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982

[3] Kochetov Yu. A., “Vychislitelnye vozmozhnosti lokalnogo poiska v kombinatornoi optimizatsii”, Zh. vychisl. matem. i matem. fiz., 48:5 (2008), 788–807 | MR | Zbl

[4] Kochetov Yu. A., Paschenko M. G., Plyasunov A. V., “O slozhnosti lokalnogo poiska v zadache o $p$-mediane”, Diskret. analiz i issled. operatsii. Ser. 2, 12:2 (2005), 44–71 | MR | Zbl

[5] Arya V., Garg N., Khandekar R., Meyerson A., Munagala K., Pandit V., “Local search heuristics for $k$-median and facility location problems”, Proc. 33rd Annual ACM Symp. Theory of Comput. (2001), 21–29 | MR

[6] Charikar M., Guha S., Tardos E., Shmoys D. B., “A constant-factor approximation algorithm for the $k$-median problem”, Proc. 31st Annual ACM Symp. Theory of Comput. (1999), 1–10 | MR

[7] Charikar M., Guha S., “Improved combinatorial algorithms for the facility location and $k$-median problems”, Proc. 40th Annual IEEE Symp. Foundations of Computer Sci. (1999), 378–388 | MR

[8] Jain K., Vazirani V. V., “Primal-dual approximation algorithms for metric facility location and $k$-median problems”, Proc. 40th Annual IEEE Symp. Foundations of Computer Sci. (1999), 2–13 | MR

[9] Nemhauser G. L., Wolsey L. A., Integer and combinatorial optimization, John Wiley Sons Inc., New York, 1988 | MR

[10] Conforti M., Cornuejols G., “Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado–Edmonds theorem”, Discrete Appl. Math., 7:3 (1984), 251–274 | DOI | MR | Zbl

[11] Ilev V. P., “Otsenka tochnosti algoritma zhadnogo spuska dlya zadachi minimizatsii supermodulyarnoi funktsii”, Diskret. analiz i issled. operatsii. Ser. 1, 5:4 (1998), 45–60 | MR | Zbl

[12] Il'ev V. P., “An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function”, Discrete Appl. Math., 114 (2001), 131–146 | DOI | MR | Zbl

[13] Il'ev V., Linker N., “Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid”, European J. Operat. Res., 171 (2006), 648–660 | DOI | MR | Zbl

[14] Ilev V. P., Linker N. V., “K zadache minimizatsii supermodulyarnoi funktsii na komatroide”, Vestnik Omskogo un-ta, 2002, no. 1, 16–18