# Minimax and Applications

Ding-Zhu Du, Panos M. Pardalos
Springer Science & Business Media, 2013. gada 1. dec. - 296 lappuses
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.

### Lietotāju komentāri -Rakstīt atsauksmi

Ierastajās vietās neesam atraduši nevienu atsauksmi.

### Saturs

 Preface 1 The First Minimax Theorem 2 Minimax Theorems for Separately Semicontinuous Functions 4 Topological Minimax Theorems 5 Quantitative Minimax Theorems 8 Mixed Minimax Theorems 12 Unifying Metaminimax Theorems 13 Connections with Weak Compactness 15
 References 188 Heilbronn Problem for Seven Points in a Planar Convex Body 191 Propositions and Proofs for Easier Cases 192 Configurations with Stability 195 Computing the Smallest Triangle 203 Open Problems 217 References 218 On the Complexity of MinMax Optimization Problems and Their Approximation 219

 Minimax Inequalities for Two or More Functions 17 Coincidence Theorems 19 A Survey on Minimax Trees and Associated Algorithms 25 Minimax Trees and the Theory Behind Them 26 Sequential Minimax Game Tree Algorithms 31 Parallel Minimax Tree Algorithms 42 Open Problems and Conclusion 51 References 52 An Iterative Method for the Minimax Problem 55 An ELQP Problem as a Subproblem 56 Local and Superlinear Convergence 60 References 66 A Dual and Interior Point Approach 68 Concluding Remarks 77 References 96 A Best Algorithm for O2pmtnCmax 103 Concepts and models 110 Discussion 117 References 127 Mutually Repellant Sampling 129 128 MaxAverage Distance Sampling 136 Problem Statement and Geometry 142 Stationary Points and Local Minima 148 Conclusions 156 The Minmax Resource Allocation Problem 162 Summary and Extensions 169 Proof of the Main Theorem 179
 Definition 221 IICompleteness Results 223 Approximation Problems and Their Hardness 231 Nonapproximability Results 233 Conclusion and Open Questions 238 References 239 A Competitive Algorithm for the Counterfeit Coin Problem 241 d 242 A Competitive Algorithm 244 Analysis of Competitiveness 247 Conclusion 249 References 250 A Minimax off Relaxation for Global Optimization 251 Problem Model 252 Relaxation Approach 253 A General off Relaxation Algorithm 254 A Minimax aft Relaxation Algorithm for COP 258 Experimental Results 263 References 268 Minimax Problems in Combinatorial Optimization 269 Algorithmic Problems 270 Geometric Problems 274 Graph Problems 281 Management Problems 287 DingZhu Du and Panos M Pardalos 288 Miscellaneous 291 Autortiesības