Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T11:12:56.591Z Has data issue: false hasContentIssue false
  • English
  • Français

Bottleneck Capacity Expansion Problems with General BudgetConstraints

Published online by Cambridge University Press:  15 August 2002

Rainer E. Burkard ,
Bettina Klinz  and
Jianzhong Zhang
Rainer E. Burkard
Affiliation:
Institut für Mathematik B, TU Graz, Steyrergasse 30, 8010 Graz, Austria.
Bettina Klinz
Affiliation:
Institut für Mathematik B, TU Graz, Steyrergasse 30, 8010 Graz, Austria.
Jianzhong Zhang
Affiliation:
Department of Mathematics, City University of Hong Kong, Hong Kong.
Get access

Abstract

This paper presents a unified approach forbottleneckcapacity expansion problems. In the bottleneck capacity expansion problem, BCEP, we are given a finite ground set E, a family Fof feasible subsets of E and a nonnegative real capacity ĉefor all e ∈ E. Moreover, we are given monotone increasing cost functions f e for increasing the capacity of the elements e ∈ E as well as a budget B. The task is to determine new capacities ce ≥ ĉe such that the objective function given by maxF∈F mine∈F ce is maximized under the sideconstraint that the overall expansion cost does not exceed the budget B.We introduce an algebraic model for defining the overall expansion cost and for formulating the budget constraint. This models allows to capturevarious types of budget constraints in one general model.Moreover, wediscuss solution approaches for the general bottleneck capacityexpansion problem. For an important subclass of bottleneck capacity expansion problems we propose algorithms which perform a strongly polynomial number ofsteps. In this manner we generalize and improve a recent result ofZhang et al. [15].

Keywords

Capacity expansionbottleneck problemstrongly polynomial algorithmalgebraic optimization.
Type
Research Article
Information
RAIRO - Operations Research , Volume 35 , Issue 1 , January 2001 , pp. 1 - 20
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ahuja, R.K. and Orlin, J.B., A capacity scaling algorithm for the constrained maximum flow problem. Networks 25 (1995) 89-98. CrossRef
Burkard, R.E., Dlaska, K. and Klinz, B., The quickest flow problem. Z. Oper. Res. (ZOR) 37 (1993) 31-58.
Burkard, R.E., Hahn, W. and Zimmermann, U., An algebraic approach to assignment problems. Math. Programming 12 (1977) 318-327. CrossRef
R.E. Burkard and U. Zimmermann, Combinatorial optimization in linearly ordered semimodules: A survey, in Modern Applied Mathematics, edited by B. Korte. North Holland, Amsterdam (1982) 392-436.
Drangmeister, K.U., Krumke, S.O., Marathe, M.V., Noltemeier, H. and Ravi, S.S., Modifying edges of a network to obtain short subgraphs. Theoret. Comput. Sci. 203 (1998) 91-121. CrossRef
Frederickson, G.N. and Solis-Oba, R., Increasing the weight of minimum spanning trees. J. Algorithms 33 (1999) 244-266. CrossRef
G.N. Frederickson and R. Solis-Oba, Algorithms for robustness in matroid optimization, in Proc. of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (1997) 659-668.
Fulkerson, D.R. and Harding, G.C., Maximizing the minimum source-sink path subject to a budget constraint. Math. Programming 13 (1977) 116-118. CrossRef
A. Jüttner, On budgeted optimization problems. Private Communication (2000).
Krumke, S.O., Marathe, M.V., Noltemeier, H., Ravi, R. and Ravi, S.S., Approximation algorithms for certain network improvement problems. J. Combin. Optim. 2 (1998) 257-288. CrossRef
Megiddo, N., Combinatorial optimization with rational objective functions. Math. Oper. Res. 4 (1979) 414-424. CrossRef
Megiddo, N., Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30 (1983) 852-865. CrossRef
C. Phillips, The network inhibition problem, in Proc. of the 25 th Annual Symposium on the Theory of Computing (1993) 776-785.
T. Radzik, Parametric flows, weighted means of cuts, and fractional combinatorial optimization, in Complexity in Numerical Optimization, edited by P.M. Pardalos. World Scientific Publ. (1993) 351-386.
Zhang, J., Yang, C. and Lin, Y., A class of bottleneck expansion problems. Comput. Oper. Res. 28 (2001) 505-519. CrossRef
U. Zimmermann, Linear and Combinatorial Optimization in Ordered Algebraic Structures. North-Holland, Amsterdam, Ann. Discrete Math. 10 (1981).