Constrained balanced optimization problems. (English) Zbl 0931.90042
Summary: We consider the balanced optimization problem with an additional linear constraint under a general combinatorial optimization setting. It is shown that this Constrained Balanced Optimization Problem (CBOP) can be solved in polynomial time whenever an associated minsum problem can be solved in polynomial time. A modification of this basic algorithm is also suggested with improved average performance. This modified algorithm is applicable to the unconstrained version also and has better average performance than existing algorithms. computational results are presented which establish the superiority of the modified algorithm on both, constrained and unconstrained models. Some variants of CBOP are also discussed in brief.
MSC:
| 90C27 | Combinatorial optimization |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Martins, E. Q.V., An algorithm to determine a path with minimal cost/capacity ratio, Discrete Applied Mathematics, 8, 189-194 (1984) · Zbl 0572.90098 |
| [2] | Galil, Z.; Schieber, B., On finding most uniform spanning trees, Discrete Applied Mathematics, 20, 173-175 (1988) · Zbl 0645.05035 |
| [3] | Camerini, P. M.; Maffioli, F.; Martello, S.; Toth, P., Most and least uniform spanning trees, Discrete Applied Mathematics, 21, 707-716 (1986) |
| [4] | Katoh, N., An ϵ-approximation scheme for combinatorial problems with variance criterion, Discrete Applied Mathematics, 35, 131-141 (1992) · Zbl 0751.90062 |
| [5] | Martello, S.; Pulleyblank, W. R.; Toth, P.; de Werra, D., Balanced optimization problems, Operations Research Letters, 3, 275-278 (1984) · Zbl 0554.90078 |
| [6] | Zeitlin, Z., Minimization of maximum absolute deviation in integers, Discrete Applied Mathematics, 3, 203-220 (1981) · Zbl 0471.90075 |
| [7] | Duin, C. W.; Volgenant, A., Minimum deviation and balanced optimization: A unified approach, Operations Research Letters, 10, 43-48 (1991) · Zbl 0729.90072 |
| [8] | Punnen, A. P., On combined minmax-minsum optimization, Computers and Operations Research, 21, 707-716 (1994) · Zbl 0810.90109 |
| [9] | Ahuja, R. K., Minimum cost to reliability ratio problem, Computers and Operations Research, 83-89 (1988) · Zbl 0643.90088 |
| [10] | Bertsekas, D. P., Linear Network Optimization: Algorithms and Codes (1991), MIT Press: MIT Press Cambridge, MA · Zbl 0754.90059 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
