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.

Klappentext

Classical minimax theory (von Neumann), duality and saddle point analysis have together played a critical role in optimization and game theory. It is currently recognised that minimax problems and techniques appear throughout a broad spectrum of disciplines, including game theory, optimization, and computational complexity. Many interesting and sophisticated problems are formulated as minimax applications, as in the fields of combinatorial optimization, scheduling, location, packing, searching, and triangulation. The contributions to Minimax and Applications cover a wide range of topics and provide an excellent picture of recent research and developments in minimax theory. Audience: Accessible to graduate students as well as researchers in optimization, computer science, and related areas.

Zusammenfassung
` ... a valuable book carefully written in a clear and concise fashion. The survey papers give coherent and inspiring accounts ... coverage of algorithmic and applied topics ... is impressive. Both graduate students and researchers in fields such as optimization, computer science, production management, operations research and related areas will find this book to be an excellent source for learning about both classic and more recent developments in minimax and its applications. The editors are to be commended for their work in gathering these papers together.'
Journal of Global Optimization, 11 (1997)

Inhalt
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.