KMS Of Academy of mathematics and systems sciences, CAS
An oracle strongly polynomial algorithm for bottleneck expansion problems | |
Zhang, JZ; Liu, ZH | |
2002-02-01 | |
Source Publication | OPTIMIZATION METHODS & SOFTWARE |
ISSN | 1055-6788 |
Volume | 17Issue:1Pages:61-75 |
Abstract | Let E = {e(1), e(2),..., e(n)} be a finite set and F be a family of subsets of E. For each element e(i) in E, c(i) is a given capacity and w(i) is the cost of increasing capacity c(i) by one unit. The problem is how to expand the capacities of elements in E so that the capacity of F is as large as possible, subject to a given budget restriction. This problem was introduced in [1] where an algorithm was proposed which is polynomial under some conditions. However, that method is not strongly polynomial. In this paper this problem is solved by solving a combinatorial equation. It is shown that if the problem min(Fis an element ofF)w(F) is solvable in strongly polynomial time, then the bottleneck expansion problem is also solvable in strongly polynomial time. This result is stronger than what the method in [1] gives. In addition, some interesting variations of this problem are also discussed. |
Keyword | bottleneck capacity capacity expansion polynomially solvable |
DOI | 10.1080/10556780290027819 |
Language | 英语 |
WOS Research Area | Computer Science ; Operations Research & Management Science ; Mathematics |
WOS Subject | Computer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied |
WOS ID | WOS:000176160600003 |
Publisher | TAYLOR & FRANCIS LTD |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/17196 |
Collection | 中国科学院数学与系统科学研究院 |
Affiliation | 1.City Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China 2.Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China |
Recommended Citation GB/T 7714 | Zhang, JZ,Liu, ZH. An oracle strongly polynomial algorithm for bottleneck expansion problems[J]. OPTIMIZATION METHODS & SOFTWARE,2002,17(1):61-75. |
APA | Zhang, JZ,&Liu, ZH.(2002).An oracle strongly polynomial algorithm for bottleneck expansion problems.OPTIMIZATION METHODS & SOFTWARE,17(1),61-75. |
MLA | Zhang, JZ,et al."An oracle strongly polynomial algorithm for bottleneck expansion problems".OPTIMIZATION METHODS & SOFTWARE 17.1(2002):61-75. |
Files in This Item: | ||||||
There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment