Inverse minimum cost flow problems under the weighted Hamming distance

CORC > 厦门大学 > 信息技术－已发表论文

	Inverse minimum cost flow problems under the weighted Hamming distance
	Jiang, Y. W. ; Liu, L. C. ; Wu, B. A. ; Yao, E. Y. ; Liu LC(刘龙城)
刊名	http://dx.doi.org/10.1016/j.ejor.2010.03.029
	2010-11-16
关键词	SPANNING TREE PROBLEMS
英文摘要	Natural Science Foundation of China [90818013]; Zhejiang Provincial Natural Science Foundation of China [Y6090175, Y6090554]; Given a network N(V,A,u,c) and a feasible flow x(0), an inverse minimum cost flow problem is to modify the cost vector as little as possible to make x(0) form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the inverse minimum cost flow problems, where the modification of the arcs is measured by the weighted Hamming distance. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in O(n . m(2)). (C) 2010 Elsevier B.V. All rights reserved.
语种	英语
内容类型	期刊论文
源URL	[http://dspace.xmu.edu.cn/handle/2288/70637]
专题	信息技术－已发表论文
推荐引用方式 GB/T 7714	Jiang, Y. W.,Liu, L. C.,Wu, B. A.,et al. Inverse minimum cost flow problems under the weighted Hamming distance[J]. http://dx.doi.org/10.1016/j.ejor.2010.03.029,2010.
APA	Jiang, Y. W.,Liu, L. C.,Wu, B. A.,Yao, E. Y.,&刘龙城.(2010).Inverse minimum cost flow problems under the weighted Hamming distance.http://dx.doi.org/10.1016/j.ejor.2010.03.029.
MLA	Jiang, Y. W.,et al."Inverse minimum cost flow problems under the weighted Hamming distance".http://dx.doi.org/10.1016/j.ejor.2010.03.029 (2010).