An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function
An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function
复制标题
DOI：
10.1016/s0166-218x(00)00366-8
复制
发表时间：
2001-10-30
影响因子：
1.1
通讯作者：
Il'ev, VP
中科院分区：
文献类型：
--
作者：
Il'ev, VP
我们考虑极小化一个超模集函数的问题，其特例是著名的NP-难p-中值问题。本文的主要结果是一个紧界的贪婪启发式（离散模拟的最速下降算法）为这个问题的近似比。(C)2001 Elsevier Science B. V.保留所有权利。
We consider the problem of minimizing a supermodular set function whose special case is the well-known NP-hard p-median problem. The main result of the paper is a tight bound on the approximation ratio of a greedy heuristic (discrete analog of the steepest descent algorithm) for this problem. (C) 2001 Elsevier Science B.V. All rights reserved.