Minimax and Applications

Pirmais vāks
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.

No grāmatas satura

Atlasītās lappuses

Saturs

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
Definition
221

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
A 2
58
Local and Superlinear Convergence
60
References
66
བྲསྤྱ
73
Concepts and models
110
Discussion
120
References
127
Mutually Repellant Sampling 129
128
MaxAverage Distance Sampling
136
min max fx
141
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
References
188
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 aß Relaxation for Global Optimization
251
Problem Model
252
Relaxation Approach
253
A General aß Relaxation Algorithm
254
A Minimax aß 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
Author Index
293
Autortiesības

Citi izdevumi - Skatīt visu

Bieži izmantoti vārdi un frāzes

Bibliogrāfiskā informācija