Matousek - Understanding and Using Linear Programming.pdf

(2247 KB) Pobierz
258740302 UNPDF
258740302.001.png
258740302.002.png
Jirí Matoušek
Bernd Gärtner
Understanding and Using
Linear Programming
ABC
Jirí Matoušek
Department of Applied Mathematics
Charles University
Malostranské nám. 25
118 00 Praha 1, Czech Republic
E-mail: matousek@kam.mff.cuni.cz
Bernd Gärtner
Institute of Theoretical Computer Science
ETH Zurich
CH-8092 Zurich, Switzerland
E-mail: gaertner@inf.ethz.ch
Mathematics Subject Classification (2000): 90C05
Library of Congress Control Number: 2006931795
ISBN-10 3-540-30697-8 Springer Berlin Heidelberg New York
ISBN-13 978-3-540-30697-9 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting,
reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9,
1965, in its current version, and permission for use must always be obtained from Springer. Violations are
liable for prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media
springer.com
c
SPIN: 11592457 46/techbooks 543210
Springer-Verlag Berlin Heidelberg 2007
The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply,
even in the absence of a specific statement, that such names are exempt from the relevant protective laws
and regulations and therefore free for general use.
Typesetting: by the authors and techbooks using a Springer T E X macro package
Cover design: design & production GmbH, Heidelberg
Printed on acid-free paper
258740302.003.png
Preface
This is an introductory textbook of linear programming, written mainly for
students of computer science and mathematics. Our guiding phrase is, “what
every theoretical computer scientist should know about linear programming.”
The book is relatively concise, in order to allow the reader to focus on
the basic ideas. For a number of topics commonly appearing in thicker books
on the subject, we were seriously tempted to add them to the main text, but
we decided to present them only very briefly in a separate glossary. At the
same time, we aim at covering the main results with complete proofs and in
sucient detail, in a way ready for presentation in class.
One of the main focuses is applications of linear programming, both in
practice and in theory. Linear programming has become an extremely flex-
ible tool in theoretical computer science and in mathematics. While many
of the finest modern applications are much too complicated to be included
in an introductory text, we hope to communicate some of the flavor (and
excitement) of such applications on simpler examples.
We present three main computational methods. The simplex algorithm is
first introduced on examples, and then we cover the general theory, putting
less emphasis on implementation details. For the ellipsoid method we give
the algorithm and the main claims required for its analysis, omitting some
technical details. From the vast family of interior point methods, we concen-
trate on one of the most ecient versions known, the primal–dual central
path method, and again we do not present the technical machinery in full.
Rigorous mathematical statements are clearly distinguished from informal
explanations in such parts.
The only real prerequisite to this book is undergraduate linear algebra.
We summarize the required notions and results in an appendix. Some of the
examples also use rudimentary graph-theoretic terminology, and at several
places we refer to notions and facts from calculus; all of these should be a
part of standard undergraduate curricula.
Errors. If you find errors in the book, especially serious ones, we would
appreciate it if you would let us know (email: matousek@kam.mff.cuni.cz ,
gaertner@inf.ethz.ch ). We plan to post a list of errors at http://www.
inf.ethz.ch/personal/gaertner/lpbook .

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin