Approximate solution of the $p$-median minimization problem

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.