Combinatorial Optimization_ Theory and Algorithms (3rd ed.) [Korte & Vygen 2005-09-01].pdf

(16317 KB) Pobierz
Algorithms and Combinatorics 21
Editorial Board
R.L. Graham, La Jolla B. Korte, Bonn
L. Lovász, Budapest A. Wigderson, Princeton
G.M. Ziegler, Berlin
Bernhard Korte
Jens Vygen
Combinatorial
Optimization
Theory and Algorithms
Third Edition
1
2
3
Bernhard Korte
Jens Vygen
Research Institute for Discrete Mathematics
University of Bonn
Lennéstraße 2
53113 Bonn, Germany
e-mail: dm@or.uni-bonn.de
vygen@or.uni-bonn.de
Library of Congress Control Number: 2005931374
Mathematics Subject Classification (2000):
90C27, 68R10, 05C85, 68Q25
ISSN 0937-5511
ISBN-10 3-540-25684-9 Springer-Verlag Berlin Heidelberg New York
ISBN-13 978-3-540-25684-7 Springer-Verlag Berlin Heidelberg New York
ISBN 3-540-43154-3 2nd ed. Springer-Verlag 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 microfilms 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
springeronline.com
© Springer-Verlag Berlin Heidelberg 2000, 2002, 2006
Printed in Germany
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.
a
Typeset in
L T X
by the authors. Edited and reformatted by Kurt Mattes, Heidelberg, using the
E
a
E
MathTime fonts and a Springer
L T X
macro package.
Production: LE-
TEX
Jelonek, Schmidt & Vöckler GbR, Leipzig
Cover design:
design & production
GmbH, Heidelberg
Printed on acid-free paper
46/3142YL - 5 4 3 2 1 0
Preface to the Third Edition
After five years it was time for a thoroughly revised and substantially extended
edition. The most significant feature is a completely new chapter on facility loca-
tion. No constant-factor approximation algorithms were known for this important
class of
NP-hard
problems until eight years ago. Today there are several interesting
and very different techniques that lead to good approximation guarantees, which
makes this area particularly appealing, also for teaching. In fact, the chapter has
arisen from a special course on facility location.
Many of the other chapters have also been extended significantly. The new ma-
terial includes Fibonacci heaps, Fujishige’s new maximum flow algorithm, flows
over time, Schrijver’s algorithm for submodular function minimization, and the
Robins-Zelikovsky Steiner tree approximation algorithm. Several proofs have been
streamlined, and many new exercises and references have been added.
We thank those who gave us feedback on the second edition, in particular
Takao Asano, Yasuhito Asano, Ulrich Brenner, Stephan Held, Tomio Hirata, Dirk
M¨ ller, Kazuo Murota, Dieter Rautenbach, Martin Skutella, Markus Struzyna and
u
J¨ rgen Werber, for their valuable comments. Eminently, Takao Asano’s notes and
u
J¨ rgen Werber’s proofreading of Chapter 22 helped to improve the presentation at
u
various places.
Again we would like to mention the Union of the German Academies of
Sciences and Humanities and the Northrhine-Westphalian Academy of Sciences.
Their continuous support via the long-term project “Discrete Mathematics and Its
Applications” funded by the German Ministry of Education and Research and the
State of Northrhine-Westphalia is gratefully acknowledged.
Bonn, May 2005
Bernhard Korte and Jens Vygen

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin