caa a22 4500 445839678 CHVBK 20180317145340.0 cr unu---uuuuu 170323e20110201xx s 000 0 eng 10.1007/s00186-010-0331-4 doi (NATIONALLICENCE)springer-10.1007/s00186-010-0331-4 On generalized balanced optimization problems [Elektronische Daten] [Lara Turner, Abraham Punnen, Yash Aneja, Horst Hamacher] In the generalized balanced optimization problem (GBaOP) the objective value $${\max_{e \in S}{|c(e)-k\max(S)|}}$$ is minimized over all feasible subsets S of E={1, . . . , m}. We show that the algorithm proposed in Punnen and Aneja (Oper Res Lett 32:27-30, 2004) can be modified to ensure that the resulting solution is indeed optimal. This modification is attained at the expense of increased worst-case complexity, but still maintains polynomial solvability of various special cases that are of general interest. In particular, we show that GBaOP can be solved in polynomial time if an associated bottleneck problem can be solved in polynomial time. For the solution of this bottleneck problem, we propose two alternative approaches. Springer-Verlag, 2010 Combinatorial optimization nationallicence Balanced optimization nationallicence Bottleneck problems nationallicence Turner Lara Department of Mathematics, Technical University of Kaiserslautern, P. O. Box 3049, 67653, Kaiserslautern, Germany aut Punnen Abraham Department of Mathematics, Simon Fraser University Surrey, Central City, 250-13450 102nd AV, V3T 0A3, Surrey, BC, Canada aut Aneja Yash Odette School of Business, University of Windsor, N9B 3P4, Windsor, ON, Canada aut Hamacher Horst Department of Mathematics, Technical University of Kaiserslautern, P. O. Box 3049, 67653, Kaiserslautern, Germany aut Mathematical Methods of Operations Research Springer-Verlag 73/1(2011-02-01), 19-27 1432-2994 73:1<19 2011 73 186 https://doi.org/10.1007/s00186-010-0331-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00186-010-0331-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Turner Lara Department of Mathematics, Technical University of Kaiserslautern, P. O. Box 3049, 67653, Kaiserslautern, Germany aut NATIONALLICENCE 700 1- Punnen Abraham Department of Mathematics, Simon Fraser University Surrey, Central City, 250-13450 102nd AV, V3T 0A3, Surrey, BC, Canada aut NATIONALLICENCE 700 1- Aneja Yash Odette School of Business, University of Windsor, N9B 3P4, Windsor, ON, Canada aut NATIONALLICENCE 700 1- Hamacher Horst Department of Mathematics, Technical University of Kaiserslautern, P. O. Box 3049, 67653, Kaiserslautern, Germany aut NATIONALLICENCE 773 0- Mathematical Methods of Operations Research Springer-Verlag 73/1(2011-02-01), 19-27 1432-2994 73:1<19 2011 73 186 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer