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

Lietotāju komentāri - Rakstīt atsauksmi

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

Atlasītās lappuses

Saturs

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

Citi izdevumi - Skatīt visu

Bieži izmantoti vārdi un frāzes

Bibliogrāfiskā informācija