Minimax and ApplicationsDing-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
1.–5. rezultāts no 23.
viii. lappuse
... Lower Bound for 02 || Cmax 4. An Algorithm for 02 || Cmax 5. A Best Algorithm for 02 | pmtn | Cmax 6. On Flow and Job Shops 7. Discussions References 69 69 70 བྲསྤྱ 73 77 77 79 79 ..81 83 .84 .87 .96 97 97 .98 .99 100 ..103 105 106 106 ...
... Lower Bound for 02 || Cmax 4. An Algorithm for 02 || Cmax 5. A Best Algorithm for 02 | pmtn | Cmax 6. On Flow and Job Shops 7. Discussions References 69 69 70 བྲསྤྱ 73 77 77 79 79 ..81 83 .84 .87 .96 97 97 .98 .99 100 ..103 105 106 106 ...
30. lappuse
Esat sasniedzis šīs grāmatas aplūkošanas reižu limitu.
Esat sasniedzis šīs grāmatas aplūkošanas reižu limitu.
31. lappuse
Esat sasniedzis šīs grāmatas aplūkošanas reižu limitu.
Esat sasniedzis šīs grāmatas aplūkošanas reižu limitu.
32. lappuse
Esat sasniedzis šīs grāmatas aplūkošanas reižu limitu.
Esat sasniedzis šīs grāmatas aplūkošanas reižu limitu.
33. lappuse
Esat sasniedzis šīs grāmatas aplūkošanas reižu limitu.
Esat sasniedzis šīs grāmatas aplūkošanas reižu limitu.
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 |
17 | |
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 |
Citi izdevumi - Skatīt visu
Bieži izmantoti vārdi un frāzes
3-partition problem a₁ alpha-beta algorithm approximation algorithms aß relaxation algorithm assume bilevel programming clause compact complexity compute constraints convex cones convex hull convex set counterfeit coin defined denote distance edges ELQP Euclidean exists feasible finite game trees given graph G grid graph Hamiltonian circuit Heilbronn Heilbronn numbers hence II-complete iteration Kindler Lemma linear log₂ loop lower semicontinuous Math Mathematical maximum minimax algorithm minimax problem minimax theorem minimax tree minimax value minimize minimum MMPC MMRA MMST nonempty NP-complete NP-hard objective function optimal solution optimization problems parallel minimax Pardalos partition peripheral triangles points polynomial polynomial-time processors Proof prove pseudo-polynomial r₁ result satisfies scenario scheduling solved spanning tree Steiner network subgraph subsets subtree Suppose theory tight topological space triples truth assignment upper bound variables vertex vertices w(Tn X-literal y₁