Theory of Linear and Integer Programming (Paperback)

Theory of Linear and Integer Programming Alexander Schrijver Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands This book describes the theory of linear and integer programming and surveys the algorithms for linear and integer programming problems, focusing on complexity analysis. It aims at complementing the more practically oriented books in this field. A special feature is the authora s coverage of important recent developments in linear and integer programming. Applications to combinatorial optimization are given, and the author also includes extensive historical surveys and bibliographies. The book is intended for graduate students and researchers in operations research, mathematics and computer science. It will also be of interest to mathematical historians. Contents 1 Introduction and preliminaries; 2 Problems, algorithms, and complexity; 3 Linear algebra and complexity; 4 Theory of lattices and linear diophantine equations; 5 Algorithms for linear diophantine equations; 6 Diophantine approximation and basis reduction; 7 Fundamental concepts and results on polyhedra, linear inequalities, and linear programming; 8 The structure of polyhedra; 9 Polarity, and blocking and anti--blocking polyhedra; 10 Sizes and the theoretical complexity of linear inequalities and linear programming; 11 The simplex method; 12 Primal--dual, elimination, and relaxation methods; 13 Khachiyana s method for linear programming; 14 The ellipsoid method for polyhedra more generally; 15 Further polynomiality results in linear programming; 16 Introduction to integer linear programming; 17 Estimates in integer linear programming; 18 The complexity of integer linear programming; 19 Totally unimodular matrices: fundamental properties and examples; 20 Recognizing total unimodularity; 21 Further theory related to total unimodularity; 22 Integral polyhedra and total dual integrality; 23 Cutting planes; 24 Further methods in integer linear programming; Historical and further notes on integer linear programming; References; Notation index; Author index; Subject index

《線性和整數規劃理論》亞歷山大·斯克賴弗（Alexander Schrijver）阿姆斯特丹數學與計算機科學研究中心，荷蘭 本書描述了線性和整數規劃的理論，並概述了線性和整數規劃問題的算法，重點是複雜性分析。它旨在補充這一領域中更實際導向的書籍。作者特別介紹了線性和整數規劃的重要最新發展。書中提供了組合優化的應用，作者還包括了廣泛的歷史調查和文獻資料。本書適用於運籌學、數學和計算機科學的研究生和研究人員，也對數學歷史學家具有興趣。 目錄 1 引言和預備知識；2 問題、算法和複雜性；3 線性代數和複雜性；4 格和線性丟番圖方程的理論；5 線性丟番圖方程的算法；6 丟番圖逼近和基底縮減；7 多面體、線性不等式和線性規劃的基本概念和結果；8 多面體的結構；9 極性、阻塞和反阻塞多面體；10 線性不等式和線性規劃的理論複雜性和大小；11 簡單法；12 原始-對偶、消除和鬆弛方法；13 Khachiyana 的線性規劃方法；14 多面體的橢圓體法更一般地；15 線性規劃中的進一步多項式結果；16 整數線性規劃簡介；17 整數線性規劃的估計；18 整數線性規劃的複雜性；19 完全單調矩陣：基本性質和例子；20 識別完全單調性；21 與完全單調性相關的進一步理論；22 整數多面體和完全對偶整數性；23 切割平面；24 整數線性規劃的進一步方法；整數線性規劃的歷史和進一步註釋；參考文獻；符號索引；作者索引；主題索引