Approximation Algorithms
In this chapter we introduce the important concept of approximation algorithms. So far we have dealt mostly with polynomially solvable problems. In the remaining chapters we shall indicate some strategies to cope with NP-hard combinatorial optimization pr
- PDF / 44,089,872 Bytes
- 534 Pages / 441.711 x 665.373 pts Page_size
- 85 Downloads / 222 Views
Algorithms and Combinatorics 21
Editorial Board
R.L. Graham, La Jolla B. Korte, Bonn L. Lovasz, Budapest A.Wigderson, Princeton G.M. Ziegler, Berlin
Springer-Verlag Berlin Heidelberg GmbH
Bernhard Korte Jens Vygen
Combinatorial Optimization Theory and Algorithms
,
Springer
Bernhard Korte
Iens Vygen
Research Institute for Discrete Mathematics University of Bonn LennestraBe 2 53113 Bonn, Germany e-mail: [email protected] [email protected]
Cataloging-in-Publication Data applied for Oie Deutsche Bibliothek - CIP-Einheitsaufnahme Korte, Bernhard: Combinatorial optimization: theory and algorithms / Bernhard Korte; lens Vygen_ (Algorithms and combinatories; 21)
ISBN 978-3-662-21710-8 ISBN 978-3-662-21708-5 (eBook) DOI 10.1007/978-3-662-21708-5
Mathematics Subject Classification (1991): 90C27, 68R10, 05C85, 68Q25 ISSN 0937-5511 ISBN 978-3-662-21710-8 This workis subject to copyright. AII rights are reserved, whetherthewhole or part ofthe material is concerned, specifically the rights of translation, reprinting, reuse of iIIustrations, recitation, broadcasting, reproduction on mierofilms 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 ofSeptember 9, '965, in its currentversion, and permission for use must always be obtained from Springer-VerlagBerlinHeidelbergGmbH. Violations are Iiable for prosecution under the German Copyright Law. © Springer-Verlag Berlin Heidelberg 2000
Originally published by Springer-Verlag Berlin Heidelberg New York in 2000 Softcover reprint ofthe hardcover Ist edition 2000 Typeset in LATEX by the authors. Edited and reformatted by Kurt Mattes, Heidelberg, using the MathTime fonts and a Springer LATEX macro package. Printed on acid-free paper SPIN 10747400 46/3143LK - 5432 1 o
Preface
Combinatorial optimization is one of the youngest and most active areas of discrete mathematics, and is probably its driving force today. It became a subject in its own right about 50 years ago. This book describes the most important ideas, theoretical results, and algorithms in combinatorial optimization. We have conceived it as an advanced graduate text which can also be used as an up-to-date reference work for current research. The book includes the essential fundamentals of graph theory, linear and integer programming, and complexity theory. It covers classical topics in combinatorial optimization as well as very recent ones. The emphasis is on theoretical results and algorithms with provably good performance. Applications and heuristics are mentioned only occasionally. Combinatorial optimization has its roots in combinatorics, operations research, and theoretical computer science. A main motivation is that thousands of real-life problems can be formulated as abstract combinatorial optimization problems. We focus on the detailed study of classical problems which occur in many different contexts, together with the underlying theory. Most combinatorial optimization problems can be