Approximate solution of the p-median minimization problem


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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

Supplementary Files
Action
1. JATS XML

Copyright (c) 2016 Pleiades Publishing, Ltd.