Optimization Theory is an active area of research with numerous applications; many of the books are designed for engineering classes, and thus have an emphasis on problems from such fields. Covering much of the same material, there is less emphasis on coding and detailed applications as the intended audience is more mathematical. There are still several important problems discussed (especially scheduling problems), but there is more emphasis on theory and less on the nuts and bolts of coding. A constant theme of the text is the “why” and the “how” in the subject. Why are we able to do a calculation efficiently? How should we look at a problem? Extensive effort is made to motivate the mathematics and isolate how one can apply ideas/perspectives to a variety of problems. As many of the key algorithms in the subject require too much time or detail to analyze in a first course (such as the run-time of the Simplex Algorithm), there are numerous comparisons to simpler algorithms which students have either seen or can quickly learn (such as the Euclidean algorithm) to motivate the type of results on run-time savings.
Steven J. Miller, Williams College, Williamstown, MA
•Acknowledgements 14 • Preface 16 • Course Outlines 20 • Part 1. Classical Algorithms 24 Chapter 1. Efficient Multiplication, I 26 1.1. Introduction 26 1.2. Babylonian Multiplication 27 1.3. Horner's Algorithm 28 1.4. Fast Multiplication 29 1.5. Strassen's Algorithm 31 1.6. Eigenvalues, Eigenvectors and the Fibonacci Numbers 32 1.7. Exercises 34 Chapter 2. Efficient Multiplication, II 44 2.1. Binomial Coefficients 44 2.2. Pascal's Triangle 45 2.3. Dimension 47 2.4. From the Pascal to the Sierpinski Triangle 49 2.5. The Euclidean Algorithm 51 2.6. Exercises 58 • Part 2. Introduction to Linear Programming 68 Chapter 3. Introduction to Linear Programming 70 3.1. Linear Algebra 71 3.2. Finding Solutions 73 3.3. Calculus Review: Local versus Global 74 3.4. An Introduction to the Diet Problem 77 3.5. Solving the Diet Problem 78 3.6. Applications of the Diet Problem 82 3.7. Exercises 83 Chapter 4. The Canonical Linear Programming Problem 90 4.1. Real Analysis Review 91 4.2. Canonical Forms and Quadratic Equations 93 4.3. Canonical Forms in Linear Programming: Statement 94 4.4. Canonical Forms in Linear Programming: Conversion 96 4.5. The Diet Problem: Round 2 98 4.6. A Short Theoretical Aside: Strict Inequalities 99 4.7. Canonical is Not Always Best 100 4.8. The Oil Problem 101 4.9. Exercises 102 Chapter 5. Symmetries and Dualities 106 5.1. Tic-Tac-Toe and a Chess Problem 106 5.2. Duality and Linear Programming 110 5.3. Appendix: Fun Versions of Tic-Tac-Toe 111 5.4. Exercises 113 Chapter 6. Basic Feasible and Basic Optimal Solutions 118 6.1. Review of Linear Independence 118 6.2. Basic Feasible and Basic Optimal Solutions 119 6.3. Properties of Basic Feasible Solutions 120 6.4. Optimal and Basic Optimal Solutions 122 6.5. Efficiency and Euclid's Prime Theorem 123 6.6. Exercises 125 Chapter 7. The Simplex Method 130 7.1. The Simplex Method: Preliminary Assumptions 130 7.2. The Simplex Method: Statement 131 7.3. Phase II implies Phase I 132 7.4. Phase II of the Simplex Method 133 7.5. Run-time of the Simplex Method 136 7.6. Efficient Sorting 136 7.7. Exercises 138 • Part 3. Advanced Linear Programming 142 Chapter 8. Integer Programming 144 8.1. The Movie Theater Problem 145 8.2. Binary Indicator Variables 148 8.3. Logical Statements 149 8.4. Truncation, Extrema and Absolute Values 151 8.5. Linearizing Quadratic Expressions 153 8.6. The Law of the Hammer and Sudoku 154 8.7. Bus Route Example 157 8.8. Exercises 158 Chapter 9. Integer Optimization 166 9.1. Maximizing a Product 166 9.2. The Knapsack Problem 169 9.3. Solving Integer Programs: Branch and Bound 170 9.4. Exercises 173 Chapter 10. Multi-Objective and Quadratic Programming 176 10.1. Multi-Objective Linear Programming 176 10.2. Quadratic Programming 177 10.3. Example: Quadratic Objective Function 178 10.4. Removing Quadratic (and Higher Order) Terms in Constraints 179 10.5. Summary 180 10.6. Exercises 180 Chapter 11. The Traveling Salesman Problem 184 11.1. Integer Linear Programming Version of the TSP 184 11.2. Greedy Algorithm to the TSP 187 11.3. The Insertion Algorithm 188 11.4. Sub-problems Method 189 11.5. Exercises 190 Chapter 12. Introduction to Stochastic Linear Programming 192 12.1. Deterministic and Stochastic Oil Problems 193 12.2. Expected Value approach 194 12.3. Recourse Approach 195 12.4. Probabilistic Constraints 197 12.5. Exercises 198 • Part 4 . Fixed Point Theorems 200 Chapter 13. Introduction to Fixed Point Theorems 202 13.1. Definitions and Uses 202 13.2. Examples 204 13.3. Real Analysis Preliminaries 205 13.4. One-Dimensional Fixed Point Theorem 207 13.5. Newton's Method versus Divide and Conquer 209 13.6. Equivalent Regions and Fixed Points 211 13.7. Exercises 214 Chapter 14. Contraction Maps 224 14.1. Definitions 224 14.2. Fixed Points of Contraction Maps 225 14.3. Introduction to Differential Equations 228 14.4. Real Analysis Review 231 14.5. First Order Differential Equations Theorem 233 14.6. Examples of Picard's Iteration Method 236 14.7. Exercises 238 Chapter 15. Sperner's Lemma 244 15.1. Statement of Sperner's Lemma 244 15.2. Proof Strategies for Sperner's Lemma 247 15.3. Proof of Sperner's Lemma 249 15.4. Rental Harmony 251 15.5. Exercises 254 Chapter 16. Brouwer's Fixed Point Theorem 262 16.1. Bolzano-Weierstrass Theorem 262 16.2. Barycentric Coordinates 263 16.3. Preliminaries for Brouwer's Fixed Point Theorem 264 16.4. Proof of Brouwer's Fixed Point Theorem 267 16.5. Nash Equilibrium 268 16.6. Exercises 272 • Part 5. Advanced Topics 276 Chapter 17. Gale-Shapley Algorithm 278 17.1. Introduction 278 17.2. Three Parties 280 17.3. Gale-Shapley Algorithm 281 17.4. Generalization 284 17.5. Applications 285 17.6. Exercises 287 Chapter 18. Interpolating Functions 290 18.1. Lagrange Interpolation 291 18.2. Interpolation Error 293 18.3. Chebyshev Polynomials and Interpolation 295 18.4. Splines 297 18.5. Exercises 301 Chapter 19. The Four Color Problem 306 19.1. A Brief History 307 19.2. Preliminaries 309 19.3. Birkhoff and the Modern Proof 316 19.4. Appel-Haken Proof 317 19.5. Computational Improvements 320 19.6. Exercises 324 Chapter 20. The Kepler Conjecture 326 20.1. Introduction 326 20.2. Sphere Packing 329 20.3. Challenges in Proving the Kepler Conjecture 331 20.4. Local Density Inequalities 333 20.5. Computer-Aided Proof 336 20.6. Exercises 338 Bibliography 340 Index 346