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.

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 RectilinearDistance.- 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 CompetitiveAlgorithm.- 4. Analysis of Competitiveness.- 5. Conclusion.- References.- A Minimax ?ß Relaxation for Global Optimization.- 1. Introduction.- 2. Problem Model.- 3. Relaxation Approach.- 4. A General ?ß Relaxation Algorithm.- 5. A Minimax ?ß 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.