Minimax and Applications

1. Front Matter

   Pages i-xiv

   PDF

2. Minimax Theorems and Their Proofs

   • Stephen Simons

   Pages 1-23

3. A Survey on Minimax Trees And Associated Algorithms

   • Claude G. Diderich, Marc Gengler

   Pages 25-54

4. An Iterative Method for the Minimax Problem

   • Liqun Qi, Wenyu Sun

   Pages 55-67

5. A Dual and Interior Point Approach to Solve Convex Min-Max Problems

   • Jos F. Sturm, Shuzhong Zhang

   Pages 69-78

6. Determining the Performance Ratio of Algorithm Multifit for Scheduling

   • Feng Cao

   Pages 79-96

7. A Study of On-Line Scheduling Two-Stage Shops

   • Bo Chen, Gerhard J. Woeginger

   Pages 97-107

8. Maxmin Formulation of the Apportionments of Seats to a Parliament

   • Thorkell Helgason, Kurt Jörnsten, Athanasios Migdalas

   Pages 109-118

9. On Shortest K-Edge Connected Steiner Networks with Rectilinear Distance

   • D. Frank Hsu, Xiao-Dong Hu, Yoji Kajitani

   Pages 119-127

10. Mutually Repellant Sampling

    • Shang-Hua Teng

    Pages 129-140

11. Geometry and Local Optimality Conditions for Bilevel Programs with Quadratic Strictly Convex Lower Levels

    • Luis N. Vicente, Paul H. Calamai

    Pages 141-151

12. The Spherical One-Center Problem

    • Guoliang Xue, Shangzhi Sun

    Pages 153-156

13. On Min-Max Optimization of a Collection of Classical Discrete Optimization Problems

    • Gang Yu, Panagiotis Kouvelis

    Pages 157-171

14. Heilbronn Problem for Six Points in a Planar Convex Body

    • Andreas W. M. Dress, Lu Yang, Zhenbing Zeng

    Pages 173-190

15. Heilbronn Problem for Seven Points in a Planar Convex Body

    • Lu Yang, Zhenbing Zeng

    Pages 191-218

16. On the Complexity of Min-Max Optimization Problems and their Approximation

    • Ker-I Ko, Chih-Long Lin

    Pages 219-239

17. A Competitive Algorithm for the Counterfeit Coin Problem

    • X. D. Hu, F. K. Hwang

    Pages 241-250

18. A Minimax αβ Relaxation for Global Optimization

    • Jun Gu

    Pages 251-268

19. Minimax Problems in Combinatorial Optimization

    • Feng Cao, Ding-Zhu Du, Biao Gao, Peng-Jun Wan, Panos M. Pardalos

    Pages 269-292

20. Back Matter

    Pages 293-293

    PDF

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.

• algorithms
• Approximation
• combinatorial optimization
• complexity
• computation
• game theory
• geometry
• networks
• optimization
• programming
• scheduling

` ... a valuable book carefully written in a clear and concise fashion. The survey papers give coherent and inspiring accounts ... coverage of algorithmic and applied topics ... is impressive. Both graduate students and researchers in fields such as optimization, computer science, production management, operations research and related areas will find this book to be an excellent source for learning about both classic and more recent developments in minimax and its applications. The editors are to be commended for their work in gathering these papers together.'
Journal of Global Optimization, 11 (1997)

• University of Minnesota, USA

  Ding-Zhu Du

• Institute of Applied Mathematics, Beijing, China

  Ding-Zhu Du

• Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA

  Panos M. Pardalos

Policies and ethics