Linear Programming Duality: An Introduction to Oriented Matroids / Edition 1

by Achim Bachem, Walter Kern

Overview

This book presents an elementary introduction to the theory of oriented matroids. The way oriented matroids are intro-
duced emphasizes that they are the most general - and hence simplest - structures for which linear Programming Duality results can be stated and proved. The main theme of the book is duality.
Using Farkas' Lemma as the basis the authors start withre-
sults on polyhedra in Rn and show how to restate the essence of the proofs in terms of sign patterns of oriented ma-
troids. Most of the standard material in Linear Programming is presented in the setting of real space as well as in the more abstract theory of oriented matroids. This approach clarifies the theory behind Linear Programming and proofs become simpler.
The last part of the book deals with the facial structure of polytopes respectively their oriented matroid counterparts.
It is an introduction to more advanced topics in oriented matroid theory. Each chapter contains suggestions for furt-
herreading and the references provide an overview of the research in this field.

Product Details

ISBN-13:	9783540554172
Publisher:	Springer Berlin Heidelberg
Publication date:	08/26/1992
Series:	Universitext
Edition description:	1992
Pages:	218
Product dimensions:	6.10(w) x 9.25(h) x 0.36(d)

Table of Contents

1 Prerequisites.- 7.1 Sets and Relations.- 10.2 Linear Algebra.- 14.3 Topology.- 15.4 Polyhedra.- 2 Linear Duality in Graphs.- 2.1 Some Definitions.- 2.2 FARKAS’ Lemma for Graphs.- 2.3 Subspaces Associated with Graphs.- 2.4 Planar Graphs.- 2.5 Further Reading.- 3 Linear Duality and Optimization.- 3.1 Optimization Problems.- 3.2 Recognizing Optimal Solutions.- 3.3 Further Reading.- 4 The FARKAS Lemma.- 4.1 A first version.- 4.2 Homogenization.- 4.3 Linearization.- 4.4 Delinearization.- 4.5 Dehomogenization.- 4.6 Further Reading.- 5 Oriented Matroids.- 5.1 Sign Vectors.- 5.2 Minors.- 5.3 Oriented Matroids.- 5.4 Abstract Orthogonality.- 5.5 Abstract Elimination Property.- 5.6 Elementary vectors.- 5.7 The Composition Theorem.- 5.8 Elimination Axioms.- 5.9 Approximation Axioms.- 5.10 Proof of FARKAS’ Lemma in OMs.- 5.11 Duality.- 5.12 Further Reading.- 6 Linear Programming Duality.- 6.1 The Dual Program.- 6.2 The Combinatorial Problem.- 6.3 Network Programming.- 6.4 Further Reading.- 7 Basic Facts in Polyhedral Theory.- 7.1 MINKOWSKI’S Theorem.- 7.2 Polarity.- 7.3 Faces of Polyhedral Cones.- 7.4 Faces and Interior Points.- 7.5 The Canonical Map.- 7.6 Lattices.- 7.7 Face Lattices of Polars.- 7.8 General Polyhedra.- 7.9 Further Reading.- 8 The Poset (O,—).- 8.1 Simplifications.- 8.2 Basic Results.- 8.3 Shellability of Topes.- 8.4 Constructibility of O.- 8.5 Further Reading.- 9 Topological Realizations.- 9.1 Linear Sphere Systems.- 9.2 A Nonlinear OM.- 9.3 Sphere Systems.- 9.4 PL Ball Complexes.- 9.5 Further Reading.

Editorial Reviews

Linear programming duality is one of the cornerstones in combinatorial optimization. The authors give an elementary introduction to oriented matroids, clarifiying the theoretical basis of linear programming and simplifying the proofs of standard results. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews