Approximate solution of the p-median minimization problem
- Authors: Il’ev V.P.1,2, Il’eva S.D.2, Navrotskaya A.A.1,2
-
Affiliations:
- Institute of Mathematics
- Omsk State University
- Issue: Vol 56, No 9 (2016)
- Pages: 1591-1597
- Section: Article
- URL: https://journal-vniispk.ru/0965-5425/article/view/178640
- DOI: https://doi.org/10.1134/S0965542516090074
- ID: 178640
Cite item
Abstract
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.
About the authors
V. P. Il’ev
Institute of Mathematics; Omsk State University
Author for correspondence.
Email: iljev@mail.ru
Russian Federation, pr. Akademika Koptyuga 4, Novosibirsk, 630090; pr. Mira 55A, Omsk, 644077
S. D. Il’eva
Omsk State University
Email: iljev@mail.ru
Russian Federation, pr. Mira 55A, Omsk, 644077
A. A. Navrotskaya
Institute of Mathematics; Omsk State University
Email: iljev@mail.ru
Russian Federation, pr. Akademika Koptyuga 4, Novosibirsk, 630090; pr. Mira 55A, Omsk, 644077
Supplementary files
