zbMATH — the first resource for mathematics

Weight reduction problems with certain bottleneck objectives. (English) Zbl 1137.90689
Summary: This paper is concerned with bottleneck weight reduction problems (WRPs) stated as follows. We are given a finite set $$E$$, a class $$\mathcal F$$ of nonempty subsets of $$E$$, a weight $$w : E \to \mathbb R^+$$ and a cost $$c: E \to \mathbb R^+$$ . For each $$e\in E$$, $$c(e)$$ stands for the cost of reducing weight $$w(e)$$ by one unit. For each subset $$F \in \mathcal F$$, the bottleneck weight of $$F$$ is $$w(F)=\min_{e\in F}\;w(e)$$. The weight of the family $$\mathcal F$$ is the maximum of $$w(F)$$ for all $$F$$ in $$\mathcal F$$. The problem is to determine new weights $$x(e) \leqslant w(e)$$ such that the weight of $$\mathcal F$$ is minimized under the constraint that the overall reduction cost does not exceed a given budget $$B$$. Similarly to capacity expansion problems, WRPs include $$\mathcal{NP}$$-hard problems. A WRP can be formulated as a parametric optimization problem over all transversal sets $$T$$ of the class $$\mathcal F$$. This leads to (strongly) polynomial solution procedures for special systems . In particular we outline a polynomial algorithm in the case when $$\mathcal F$$ is the class of all spanning trees in an undirected graph.

MSC:
 90C35 Programming involving graphs or networks 90C31 Sensitivity, stability, parametric optimization
Full Text:
References:
 [1] Berman, O; Ingco, D.I; Odoni, A.R, Improving the location of minimum facilities through network modification, Annals of operations research, 40, 1-16, (1992) · Zbl 0787.90035 [2] Berman, O; Ingco, D.I; Odoni, A.R, Improving the location of minimax facilities through network modification, Networks, 24, 31-41, (1994) · Zbl 0799.90074 [3] Burkard, R.E; Klinz, B; Zhang, J, Bottleneck capacity expansion problems with eneral budget constraints, RAIRO recherche opérationelle, 35, 1-20, (2001) · Zbl 1078.90585 [4] Burton, D; Toint, Ph.L, On an instance of the inverse shortest paths problem, Mathematical programming, 53, 45-61, (1992) · Zbl 0756.90089 [5] Drangmeister, K.U; Krumke, S.O; Marathe, M.V; Noltemeier, H; Ravi, S.S, Modifying edges of a network to obtain short subgraphs, Theoretical computer science, 203, 91-121, (1998) · Zbl 0913.68144 [6] Frederickson, G.N; Solis-Oba, R, Increasing the weight of minimum spanning trees, Journal of algorithms, 33, 244-266, (1999) · Zbl 0956.68113 [7] Fulkerson, D.R, Increasing the capacity of a network: the parametric budget problem, Management science, 5, 472-483, (1959) · Zbl 0995.90517 [8] Fulkerson, D.R; Harding, G.C, Maximizing the minimum source-sink path subject to a budget constraint, Mathematical programming, 13, 116-118, (1977) · Zbl 0366.90115 [9] C. Heuberger, Inverse optimization: A survey on problems, methods, and results. Report 219, Spezialforschungsbereich Optimierung und Kontrolle, Universität Graz und Technische Universität Graz, 2001. Available from Journal of Combinatorial Optimization, in press [10] Krumke, S.O; Marathe, M.V; Noltemeier, H; Ravi, R; Ravi, S.S, Approximation algorithms for certain network improvement problems, Journal of combinatorial optimization, 2, 257-288, (1998) · Zbl 0916.90261 [11] Krumke, S.O; Marathe, M.V; Noltemeier, H; Ravi, R; Wirth, H.-C, Upgrading bottleneck constrained forests, Discrete applied mathematics, 108, 129-142, (2001) · Zbl 0971.68007 [12] Megiddo, N, Combinatorial optimization with rational objective functions, Mathematics of operations research, 4, 414-424, (1979) · Zbl 0425.90076 [13] Megiddo, N, Applying parallel computation algorithms in the design of serial algorithms, Journal of the ACM, 30, 852-865, (1983) · Zbl 0627.68034 [14] C. Phillips, The network inhibition problem, in: Proceedings of the 25th Annual Symposium on the Theory of Computing, 1993, pp. 776-785 · Zbl 1310.90018 [15] Radzik, T, Parametric flows, weighted means of cuts, and fractional combinatorial optimization, (), 351-386 · Zbl 0968.90515 [16] Stoer, M; Wagner, F, A simple MIN-cut algorithm, Journal of the ACM, 44, 585-591, (1997) · Zbl 0891.68071 [17] Yang, C; Zhang, J, Inverse maximum capacity problem, Operations research spektrum, 20, 97-100, (1998) · Zbl 0904.90168 [18] Zhang, J; Liu, Z; Ma, Z, Some reverse location problems, European journal of operational research, 124, 77-88, (2000) · Zbl 0960.90056 [19] Zhang, J; Yang, X.G; Cai, M.C, Reverse center location problem, (), 279-294 · Zbl 0968.90048 [20] Zhang, J; Yang, C; Lin, Y, A class of bottleneck expansion problems, Computer and operations research, 28, 505-519, (2001) · Zbl 0991.90113
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.