摘要
主要讨论了逆一般中心选址问题的算法研究。对于实例是树且U为整数的情况,逆一般中心选址问题转化为逆中心选址问题。对于实例是一般简单图的情况,本文给出了一个逆一般中心选址问题转化为权重为1的S te iner树问题的拟多项式算法。并对于权w=1的S te iner树问题,本文也给出了一个近似界为43的近似算法。
We discuss the study of algorithm for the reverse general center location problem. For the case being a tree and being an integer, the reverse general center location problem can be transformed to the reverse center location problem. As to the general graph case, we give an pseudopolynomial algorithm to transform the reverse general center location problem into the Steiner tree with unit weight problem. For the Steiner tree with unit weight problem, we al~ give afactor approximation algorithm.
出处
《系统工程》
CSCD
北大核心
2006年第2期113-117,共5页
Systems Engineering
基金
国家自然科学基金资助项目(10471096)
关键词
逆一般中心选址问题
拟多项式算法Steiner树
近似算法
Reverse General Center Location Problem t Steiner Tree
pseudopolynomial Algorithm
Approximation Algorithm
