On the optimum capacity of capacity expansion problems

Chao Yang, Chunyan Hao () and Jianzhong Zhang

Mathematical Methods of Operations Research, 2007, vol. 66, issue 2, 225-233

Abstract: In this paper we consider problems of the following type: Let E = { e 1 , e 2 ,..., e n } be a finite set and $${\mathcal {F}}$$ be a family of subsets of E. For each element e i in E, c i is a given capacity and $${\mathcal {w}}$$ i is the cost of increasing capacity c i by one unit. It is assumed that we can expand the capacity of each element in E so that the capacity of family $${\mathcal {F}}$$ can be expanded to a level r. For each r, let f (r) be the efficient function with respect to the capacity r of family $${\mathcal {F}}$$ , and $${\phi(r)}$$ be the cost function for expanding the capacity of family $${\mathcal {F}}$$ to r. The goal is to find the optimum capacity value r * and the corresponding expansion strategy so that the pure efficency function $${f(r^*)-\phi(r^*)}$$ is the largest. Firstly, we show that this problem can be solved efficiently by figuring out a series of bottleneck capacity expansion problem defined by paper (Yang and Chen, Acta Math Sci 22:207–212, 2002) if f (r) is a piecewise linear function. Then we consider two variations and prove that these problems can be solved in polynomial time under some conditions. Finally the optimum capacity for maximum flow expansion problem is discussed. We tackle it by constructing an auxiliary network and transforming the problem into a maximum cost circulation problem on the auxiliary network. Copyright Springer-Verlag 2007

Keywords: Networks and graphs; Maximum capacity; Bottleneck; Polynomial algorithm (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-007-0147-z (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:66:y:2007:i:2:p:225-233

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-007-0147-z

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().