zbMATH — the first resource for mathematics

On the complexity of the exchange algorithm for minimax optimization problems. (English) Zbl 0632.90064
We present an exchange algorithm for the solution of minimax optimization problems involving convex functions. For a certain class of functions, the complexity of this algorithm is shown to be either linear in the number of functions, or at least squared in that number.

90C30 Nonlinear programming
68Q25 Analysis of algorithms and problem complexity
90B05 Inventory, storage, reservoirs
90C25 Convex programming
Full Text: DOI
[1] Z. Drezner, ”On minimax optimization problems,”Mathematical Programming 22 (1982) 227–230. · Zbl 0473.90067 · doi:10.1007/BF01581038
[2] Z. Drezner, ”Fast algorithms for the round trip location problem,”IIE Transactions 14 (1982) 243–248. · doi:10.1080/05695558208975236
[3] Z. Drezner and G.O. Wesolowsky, ”Single facilityl p distance minimax location,”SIAM Journal of Algebraic and Discrete Methods 1 (1980) 315–321. · Zbl 0501.90031 · doi:10.1137/0601036
[4] J. Elzinga and D.W. Hearn, ”Geometrical solutions for some minimax location problems”,Transportation Science 6 (1972) 379–394. · doi:10.1287/trsc.6.4.379
[5] D.W. Hearn and J. Vijay, ”Efficient algorithms for the (weighted) minimum circle problem”,Operations Research 30 (1982) 777–795. · Zbl 0486.90039 · doi:10.1287/opre.30.4.777
[6] L.S. Lasdon,Optimization theory for large systems (The McMillan Company, New York, 1970). · Zbl 0224.90038
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.