Book Details

Search page | Title Index  | Author Index

Preface | Table of Contents | MARC record  | Metadata XML  | e-Book PDF (2140 KB)
Nonlinear Discrete Optimization
Zurich Lectures in Advanced Mathematics

Shmuel Onn (Technion - Israel Institute of Technology, Haifa, Israel)

Nonlinear Discrete Optimization

An Algorithmic Theory

ISBN 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

Review in MR 2724387 (2011m:90002)