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.
1.
Introduction
2.
From Linear to Convex Maximization
3.
Graver Bases and Nonlinear Integer Programming
4.
N-Fold Integer Programming
5.
Multiway Tables and Universality
6.
Nonlinear Combinatorial Optimization
References