Minimax and Applications

Techniques and principles of minimax theory play a key role in many areas of research, including game theory, optimization, and computational complexity. In general, a minimax problem can be formulated as min max f(x, y) (1) ",EX !lEY where f(x, y) is a function defined on the product of X and Y spaces. There are two basic issues regarding minimax problems: The first issue concerns the establishment of sufficient and necessary conditions for equality minmaxf(x,y) = maxminf(x,y). (2) "'EX !lEY !lEY "'EX The classical minimax theorem of von Neumann is a result of this type. Duality theory in linear and convex quadratic programming interprets minimax theory in a different way. The second issue concerns the establishment of sufficient and necessary conditions for values of the variables x and y that achieve the global minimax function value f(x, y) = minmaxf(x, y). (3) "'EX !lEY There are two developments in minimax theory that we would like to mention.

Inhalt

Preface. Minimax theorems and their proofs; S. Simons. A survey on minimax trees and associated algorithms; C.G. Diderich, M. Gengler. An iterative method for the minimax problem; L. Qi, W. Sun. A dual and interior point approach to solve convex min-max problems; J.F. Sturm, S. Zhang. Determining the performance ratio of algorithm MULTIFIT for scheduling; F. Cao. A study of on-line scheduling two-stage shops; B. Chen, G.J. Woeginger. Maximin formulation of the apportionment of seats to parliament; T. Helgason, et al. On shortest k-edge connected Steiner networks with rectilinear distance; D.F. Hsu, et al. Mutually repellant sampling; S.-H. Teng. Geometry and local optimality conditions for bilevel programs with quadratic strictly convex lower levels; L.N. Vicente, P.H. Calamai. On the spherical one-center problem; G. Xue, S. Sun. On min-max optimization of a collection of classical discrete optimization problems; G. Xu, P. Kouvelis. Heilbronn problem for six points in a planar convex body; A.W.M. Dress, et al. Heilbronn problem for seven points in a planar convex body; L. Yang, Z. Zeng. On the complexity of min-max optimization problems and their approximation; K.-I Ko, C.L. Lin. A competitive algorithm for the counterfeit coin problem; X.-D. Hu, F.K. Hwang. A minimax alphabeta relaxation for global optimization; J. Gu. Minimax problems in combinatorial optimization; F. Cao, et al. Author index.