Book Details
Search page | Title Index
| Author Index

Shmuel Onn (Technion - Israel Institute of Technology, Haifa, Israel)
Nonlinear Discrete Optimization
An Algorithmic TheoryISBN print 978-3-03719-093-7, ISBN online 978-3-03719-593-2
DOI 10.4171/093
September 2010, 147 pages, softcover, 17 x 24 cm.
32.00 Euro
This monograph develops an algorithmic theory of nonlinear discrete optimization. It introduces a simple and useful setup which enables the polynomial time solution of broad fundamental classes of nonlinear combinatorial optimization and integer programming problems in variable dimension. An important part of this theory is enhanced by recent developments in the algebra of Graver bases. The power of the theory is demonstrated by deriving the first polynomial time algorithms in a variety of application areas within operations research and statistics, including vector partitioning, matroid optimization, experimental design, multicommodity flows, multi-index transportation and privacy in statistical databases.
The monograph is intended for graduate students and researchers. It is accessible to anyone with standard undergraduate knowledge and mathematical maturity.
Keywords: Integer programming, combinatorial optimization, optimization, linear programming, stochastic programming, randomized algorithm, approximation algorithm, polynomial time, transportation problem, multi index transportation problem, transshipment problem, multicommodity flow, congestion game, spanning tree, matroid, submodular function, matching, partitioning, clustering, polytope, zonotope, edge direction, totally unimodular matrix, test set, Graver base, contingency table, statistical table, multiway table, disclosure control, data security, privacy, algebraic statistics, experimental design, Frobenius number, Grobner base, Hilbert scheme, zero-dimensional ideal
Further Information
Review in Zentralblatt MATH 1219.90003