Springer Science & Business Media, Jul 20, 2004 - Computers - 443 pages
Optimization Theory is becoming a more and more important mathematical as well as interdisciplinary area, especially in the interplay between mathematics and many other sciences like computer science, physics, engineering, operations research, etc.
This volume gives a comprehensive introduction into the theory of (deterministic) optimization on an advanced undergraduate and graduate level. One main feature is the treatment of both continuous and discrete optimization at the same place. This allows to study the problems under different points of view, supporting a better understanding of the entire field.
Audience: The book can be adapted well as an introductory textbook into optimization theory on a basis of a two semester course; however, each of its parts can also be taught separately. Many exercises are included to increase the reader's understanding.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Constraints Lagrange Function Optimality
Parametric Aspects SemiInfinite Optimization
Convex Functions Duality Separation Theorem
Linear Inequalities Constraint Qualifications
The Simplex Method
Applications of the MaxFlow MinCut Theorem
The GaleRyserTheorem 16 2 Königs Theorem 16 3 Dilworths Theorem 16 4 Mengers Theorem 16 5 The Minimum Cost Flow Problem Integer Line...
Totally unimodular matrices Unimodularity and integer linear programming Integral polyhedra Computability the Turing machine
Running time the class P Some important decision problems 19 3 19 4 Nondeterministic Turing machines The class NP Reducibility and NPcomplete...
Polynomial time reductions NPcompleteness Cooks theorem A polynomial time algorithm for 2SAT Some NPcompleteness results
The Random Access Machine
Complexity Theory over the Real Numbers
Approximation Algorithms for
Other editions - View all
3-Dimensional Matching approximation arcs assume augmenting path bipartite graph bounded called cardinality central path Chapter choose column combinatorial complexity theory components computation configuration Consequently constraints construct contains convergence convex corresponding cost cycle decision problems define edges elements ellipsoid endpoint equation example Exercise exists feasible set feasible solution finite alphabet formula given graph G Hamiltonian Circuit hence Hint holds implies inequality input instance integral interior point interior point method iteration Lagrange multiplier latter Lemma length Let denote LICQ linear optimization problem linearly independent local minimum matrix maximal maximum matching minimal minimum Moreover natural number Newton nodes non-deterministic nonsingular Note NP-complete objective function obtain optimal value polyhedron polynomial positive definite precisely proof of Theorem prove quadratic real number Remark respect result satisfying sequence Show simplex method solvable solves Step subset symmetric totally unimodular Traveling Salesman Turing machine variables vector vertex cover vertices yields zero