A class of inverse dominant problems under weighted l(infinity) norm and an improved complexity bound for Radzik's algorithm

doi:10.1007/s10898-005-1649-y

CSpace

	A class of inverse dominant problems under weighted l(infinity) norm and an improved complexity bound for Radzik's algorithm
	Wang, Q ; Yang, XG ; Zhang, JZ
	2006-04-01
发表期刊	JOURNAL OF GLOBAL OPTIMIZATION
ISSN	0925-5001
卷号	34 期号:4 页码:551-567
摘要	In this paper, we first discuss a class of inverse dominant problems under weighted l(infinity) norm, which is how to change the original weights of elements with bounds in a finite ground set so that a given set becomes a weakly dominant set with respect to a given collection of subsets under the new weights and the largest change of the weights is minimum. This model includes a large class of improvement problems in combinatorial optimization. We propose a Newton-type algorithm for the model. This algorithm can solve the model in strongly polynomial time if the subproblem involved is solvable in strongly polynomial time. In the second part of the paper, we improve the complexity bound for Radzik's Newton-type method which is designed to solve linear fractional combinatorial optimization problems. As Radzik's method is closely related to our algorithm, this bound also estimates the complexity of our algorithm.
关键词	dominant set improvement problem inverse problem linear fractional combinatorial optimization polynomial time algorithm
DOI	10.1007/s10898-005-1649-y
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000237360700005
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/2956
专题	中国科学院数学与系统科学研究院
通讯作者	Wang, Q
作者单位	1.China Jiliang Univ, Dept Math, Hangzhou 310018, Peoples R China 2.Chinese Acad Sci, Inst Syst Sci, Beijing 100080, Peoples R China 3.City Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China
推荐引用方式 GB/T 7714	Wang, Q,Yang, XG,Zhang, JZ. A class of inverse dominant problems under weighted l(infinity) norm and an improved complexity bound for Radzik's algorithm[J]. JOURNAL OF GLOBAL OPTIMIZATION,2006,34(4):551-567.
APA	Wang, Q,Yang, XG,&Zhang, JZ.(2006).A class of inverse dominant problems under weighted l(infinity) norm and an improved complexity bound for Radzik's algorithm.JOURNAL OF GLOBAL OPTIMIZATION,34(4),551-567.
MLA	Wang, Q,et al."A class of inverse dominant problems under weighted l(infinity) norm and an improved complexity bound for Radzik's algorithm".JOURNAL OF GLOBAL OPTIMIZATION 34.4(2006):551-567.