Title	Minimax and Applications [electronic resource] / edited by Ding-Zhu Du, Panos M. Pardalos
Imprint	Boston, MA : Springer US, 1995
Connect to	http://dx.doi.org/10.1007/978-1-4613-3557-3
Descript	XIV, 296 p. online resource

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

5? -- 3. 15/4? ? ? ? 5? -- 4. 5/2? ? ? < 15/4? -- 5. ? < 2.5? -- References -- A Study of On-Line Scheduling Two-Stage Shops -- 1. Introduction -- 2. Definitions and Preliminaries -- 3. A Lower Bound for O2??max -- 4. An Algorithm for O2??max -- 5. A Best Algorithm for O2?pmtn??max -- 6. On Flow and Job Shops -- 7. Discussions -- References -- Maxmin Formulation of the Apportionments of Seats to a Parliament -- 1. Introduction -- 2. Concepts and models -- 3. Illustrative examples -- 4. Discussion -- References -- On Shortest k-Edge Connected Steiner Networks with Rectilinear Distance -- 1. Introduction -- 2. Technical Preliminaries -- 3. Main Results -- References -- Mutually Repellant Sampling -- 1. Introduction -- 2. Mutually Repellant Sampling -- 3. Max-Min Distance Sampling -- 4. Max-Min-Selection Distance Sampling -- 5. Max-Average Distance Sampling -- 6. Lower Bounds -- 7. Applications and Open Questions -- References -- Geometry and Local Optimality Conditions for Bilevel Programs with Quadratic Strictly Convex Lower Levels -- 1. Introduction -- 2. Problem Statement and Geometry -- 3. Computing the Convex Cones -- 4. Number of Convex Cones -- 5. Stationary Points and Local Minima -- 6. Conclusions and Future Work -- References -- The Spherical One-Center Problem -- 1. Introduction -- 2. Main Result -- 3. Conclusions -- References -- On Min-max Optimization of a Collection of Classical Discrete Optimization Problems -- 1. Introduction -- 2. The Min-max Spanning Tree Problem -- 3. The Min-max Resource Allocation Problem -- 4. The Min-max Production Control Problem -- 5. Summary and Extensions -- References -- Heilbronn Problem for Six Points in a Planar Convex Body -- 1. Introduction -- 2. Prerequisites -- 3. Proof of the Main Theorem -- References -- Heilbronn Problem for Seven Points in a Planar Convex Body -- 1. Introduction -- 2. Propositions and Proofs for Easier Cases -- 3. Configurations with Stability -- 4. Computing the Smallest Triangle -- 5. Open Problems -- References -- On the Complexity of Min-Max Optimization Problems and Their Approximation -- 1. Introduction -- 2. Definition -- 3. ?2P-Completeness Results -- 4. Approximation Problems and Their Hardness -- 5. Nonapproximability Results -- 6. Conclusion and Open Questions -- References -- A Competitive Algorithm for the Counterfeit Coin Problem -- 1. Introduction -- 2. Some Lower Bounds of M(n : d) -- 3. A Competitive Algorithm -- 4. Analysis of Competitiveness -- 5. Conclusion -- References -- A Minimax ?ร{159} Relaxation for Global Optimization -- 1. Introduction -- 2. Problem Model -- 3. Relaxation Approach -- 4. A General ?ร{159} Relaxation Algorithm -- 5. A Minimax ?ร{159} Relaxation Algorithm for COP -- 6. Experimental Results -- References -- Minimax Problems in Combinatorial Optimization -- 1. Introduction -- 2. Algorithmic Problems -- 3. Geometric Problems -- 4. Graph Problems -- 5. Management Problems -- 6. Miscellaneous -- Author Index