Approximate solution of the p-median minimization problem

被引：0
作者：
V. P. Il’ev
S. D. Il’eva
A. A. Navrotskaya
机构：
[1] Siberian Branch of the Russian Academy of Sciences,Institute of Mathematics
[2] Omsk State University,undefined
来源：
Computational Mathematics and Mathematical Physics | 2016年 / 56卷
关键词：
combinatorial optimization; -median; supermodular set function; gradient algorithm; performance guarantee;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：1591 / 1597
页数：6
相关论文
共 14 条
[1]  
Kariv O.(1979)An algorithmic approach to network location problems. II. The p-medians SIAM J. Appl. Math. 37 539-560
[2]  
Hakimi S. L.(2008)Computational bounds for local search in combinatorial optimization Comput. Math. Math. Phys. 48 747-763
[3]  
Kochetov Yu. A.(2005)On the complexity of the local search in the p-median problem Diskretn. Anal. Issled Oper., Ser. 2 12 44-71
[4]  
Kochetov Yu. A.(1984)Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado–Edmonds theorem Discrete Appl. Math. 7 251-274
[5]  
Pashchenko M. G.(1998)Performance guarantee bound of a greedy descent algorithm for minimization of the supermodular function Diskretn. Anal. Issled Oper., Ser. 1 5 45-60
[6]  
Plyasunov A. V.(2001)An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function Discrete Appl. Math. 114 131-146
[7]  
Conforti M.(2006)Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid Eur J. Oper. Res. 171 648-660
[8]  
Cornuejols G.(2002)On the minimization of a supermodular function on a comatroid Vest. Omsk Univ. 1 18-18
[9]  
Il’ev V. P.(undefined)undefined undefined undefined undefined-undefined
[10]  
Il’ev V. P.(undefined)undefined undefined undefined undefined-undefined
12