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 |
| 刊名 | JOURNAL OF GLOBAL OPTIMIZATION
 |
| 出版日期 | 2006-04-01 |
| 卷号 | 34期号:4页码:551-567 |
| 关键词 | dominant set improvement problem inverse problem linear fractional combinatorial optimization polynomial time algorithm |
| ISSN号 | 0925-5001 |
| DOI | 10.1007/s10898-005-1649-y |
| 英文摘要 | 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. |
| WOS研究方向 | Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000237360700005 |
| 出版者 | SPRINGER |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/2955]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。