An oracle strongly polynomial algorithm for bottleneck expansion problems
Zhang, JZ; Liu, ZH
AbstractLet 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.
Keywordbottleneck capacity capacity expansion polynomially solvable
WOS Research AreaComputer Science ; Operations Research & Management Science ; Mathematics
WOS SubjectComputer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied
WOS IDWOS:000176160600003
Citation statistics
Document Type期刊论文
Affiliation1.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.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhang, JZ]'s Articles
[Liu, ZH]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhang, JZ]'s Articles
[Liu, ZH]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhang, JZ]'s Articles
[Liu, ZH]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.