Nonlinear discrete optimization : an algorithmic theory$nElektronische Ressource

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. This monograph is intended for graduate students and researchers. It is accessible to anyone with standard undergraduate knowledge and mathematical maturity. A publication of the European Mathematical Society (EMS). Distributed within the Americas by the American Mathematical Society. Preface......Page 7 Contents......Page 9 Introduction......Page 11 Outline of the monograph......Page 12 Nonlinear matroid problems......Page 14 Nonlinear multicommodity flows......Page 17 Complexity......Page 21 Finiteness......Page 22 Convex Discrete Maximization......Page 24 Image and fibers......Page 25 Small radius and weight......Page 28 Edge directions and zonotopes......Page 33 Efficient convex maximization......Page 36 Small radius and weight revisited......Page 38 Totally unimodular systems......Page 39 Convex combinatorial maximization......Page 41 Quadratic binary programming......Page 43 Matroids and matroid intersections......Page 44 Vector partitioning and clustering......Page 46 Graver bases......Page 50 Efficient separable convex minimization......Page 53 Distance minimization......Page 58 Convex integer maximization......Page 59 Weighted separable convex minimization......Page 60 Totally unimodular systems revisited......Page 61 Bounds on Graver bases......Page 62 n-Fold Integer Programming......Page 64 Graver bases of n-fold products......Page 65 Efficient n-fold integer programming......Page 68 Nonlinear many-commodity transshipment......Page 72 Nonlinear multicommodity transportation......Page 73 Stochastic integer programming......Page 75 Graver approximation scheme......Page 81 Multiway Tables and Universality......Page 84 The universality theorem......Page 86 Multiindex transportation problems......Page 90 Privacy in statistical databases......Page 93 Extensions to hierarchical margins......Page 96 Universality of n-fold integer programming......Page 98 Graver complexity of graphs and digraphs......Page 100 Nonlinear Combinatorial Optimization......Page 107 Preparation......Page 108 Matroids......Page 110 Matroid intersections......Page 113 Optimization over independence systems......Page 118 Approximative nonlinear optimization......Page 119 Exponential time to exact optimization......Page 127 Nonlinear bipartite matching......Page 129 Experimental design......Page 130 Universal Gröbner bases......Page 132 Bibliography......Page 139 Index......Page 145 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. 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. --Book Jacket Shmuel Onn. Includes Bibliographical References (p. [129]-134) And Index.