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 77.
xii. lappuse
... proving lower bounds : solution of Gilbert - Pollak's conjecture on the Steiner ratio , In Pro- ceedings of 31th FOCS Conference ( 1990 ) , pp . 76-85 ] . Central to this approach is a result regarding the characterization of global ...
... proving lower bounds : solution of Gilbert - Pollak's conjecture on the Steiner ratio , In Pro- ceedings of 31th FOCS Conference ( 1990 ) , pp . 76-85 ] . Central to this approach is a result regarding the characterization of global ...
2. lappuse
... proved by von Neumann in 1928 using topological arguments : Theorem 1 ( [ 124 ] ) Let A be an m × n matrix , and X and Y be the sets of nonnegative row and column vectors with unit sum . Let f ( x , y ) = x Ay . Then minmax f = max min ...
... proved by von Neumann in 1928 using topological arguments : Theorem 1 ( [ 124 ] ) Let A be an m × n matrix , and X and Y be the sets of nonnegative row and column vectors with unit sum . Let f ( x , y ) = x Ay . Then minmax f = max min ...
4. lappuse
... proved the following quasiconcave - quasiconvex u.s.c- 1.s.c result in 1958 : Theorem 3 ( [ 114 ] ) Let X be a convex ... prove Theorem 3 using a sim- ple combinatorial property of convex sets in finite dimensional space . Another very ...
... proved the following quasiconcave - quasiconvex u.s.c- 1.s.c result in 1958 : Theorem 3 ( [ 114 ] ) Let X be a convex ... prove Theorem 3 using a sim- ple combinatorial property of convex sets in finite dimensional space . Another very ...
5. lappuse
... proving the first minimax theorem in which the conditions of convexity were totally replaced by conditions related ... proved the following result that generalized both Theorem 3 and Theorem 4 . Theorem 5 ( [ 121 ] and [ 122 ] ) Let X be ...
... proving the first minimax theorem in which the conditions of convexity were totally replaced by conditions related ... proved the following result that generalized both Theorem 3 and Theorem 4 . Theorem 5 ( [ 121 ] and [ 122 ] ) Let X be ...
6. lappuse
... proved in [ 66 ] a minimax theorem for interval spaces which generalized both Theorem 7 and the result [ 29 ] of Ha already mentioned . Stachó also introduced the concept of a Dedekind complete interval space and proved a second minimax ...
... proved in [ 66 ] a minimax theorem for interval spaces which generalized both Theorem 7 and the result [ 29 ] of Ha already mentioned . Stachó also introduced the concept of a Dedekind complete interval space and proved a second minimax ...
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₁