logo资料库

Combinatorial Optimization Theory and Algorithms 6th edition.pdf

发布时间：2022-06-01 发布人：admin 分类：说明书 资料大小：11.26M 资料格式：pdf 举报 版权申诉
第1页 / 共701页
第2页 / 共701页
第3页 / 共701页
第4页 / 共701页
第5页 / 共701页
第6页 / 共701页
第7页 / 共701页
第8页 / 共701页
资料共701页，剩余部分请下载后查看
    Preface to the Sixth Edition
    Preface to the Fifth Edition
    Preface to the Fourth Edition
    Preface to the Third Edition
    Preface to the Second Edition
    Preface to the First Edition
    Table of Contents
    1 Introduction
    1.1 Enumeration
    1.2 Running Time of Algorithms
    1.3 Linear Optimization Problems
    1.4 Sorting
    Exercises
    References
    2 Graphs
    2.1 Basic Definitions
    2.2 Trees, Circuits, and Cuts
    2.3 Connectivity
    2.4 Eulerian and Bipartite Graphs
    2.5 Planarity
    2.6 Planar Duality
    Exercises
    References
    3 Linear Programming
    3.1 Polyhedra
    3.2 The Simplex Algorithm
    3.3 Implementation of the Simplex Algorithm
    3.4 Duality
    3.5 Convex Hulls and Polytopes
    Exercises
    References
    4 Linear Programming Algorithms
    4.1 Size of Vertices and Faces
    4.2 Continued Fractions
    4.3 Gaussian Elimination
    4.4 The Ellipsoid Method
    4.5 Khachiyan's Theorem
    4.6 Separation and Optimization
    Exercises
    References
    5 Integer Programming
    5.1 The Integer Hull of a Polyhedron
    5.2 Unimodular Transformations
    5.3 Total Dual Integrality
    5.4 Totally Unimodular Matrices
    5.5 Cutting Planes
    5.6 Lagrangean Relaxation
    Exercises
    References
    6 Spanning Trees and Arborescences
    6.1 Minimum Spanning Trees
    6.2 Minimum Weight Arborescences
    6.3 Polyhedral Descriptions
    6.4 Packing Spanning Trees and Arborescences
    Exercises
    References
    7 Shortest Paths
    7.1 Shortest Paths From One Source
    7.2 Shortest Paths Between All Pairs of Vertices
    7.3 Minimum Mean Cycles
    7.4 Shallow-Light Trees
    Exercises
    References
    8 Network Flows
    8.1 Max-Flow-Min-Cut Theorem
    8.2 Menger's Theorem
    8.3 The Edmonds-Karp Algorithm
    8.4 Dinic's, Karzanov's, and Fujishige's Algorithm
    8.5 The Goldberg-Tarjan Algorithm
    8.6 Gomory-Hu Trees
    8.7 The Minimum Capacity of a Cut in an Undirected Graph
    Exercises
    References
    9 Minimum Cost Flows
    9.1 Problem Formulation
    9.2 An Optimality Criterion
    9.3 Minimum Mean Cycle-Cancelling Algorithm
    9.4 Successive Shortest Path Algorithm
    9.5 Orlin's Algorithm
    9.6 The Network Simplex Algorithm
    9.7 Flows Over Time
    Exercises
    References
    10 Maximum Matchings
    10.1 Bipartite Matching
    10.2 The Tutte Matrix
    10.3 Tutte's Theorem
    10.4 Ear-Decompositions of Factor-Critical Graphs
    10.5 Edmonds' Matching Algorithm
    Exercises
    References
    11 Weighted Matching
    11.1 The Assignment Problem
    11.2 Outline of the Weighted Matching Algorithm
    11.3 Implementation of the Weighted Matching Algorithm
    11.4 Postoptimality
    11.5 The Matching Polytope
    Exercises
    References
    12 b-Matchings and T-Joins
    12.1 b-Matchings
    12.2 Minimum Weight T-Joins
    12.3 T-Joins and T-Cuts
    12.4 The Padberg-Rao Theorem
    Exercises
    References
    13 Matroids
    13.1 Independence Systems and Matroids
    13.2 Other Matroid Axioms
    13.3 Duality
    13.4 The Greedy Algorithm
    13.5 Matroid Intersection
    13.6 Matroid Partitioning
    13.7 Weighted Matroid Intersection
    Exercises
    References
    14 Generalizations of Matroids
    14.1 Greedoids
    14.2 Polymatroids
    14.3 Minimizing Submodular Functions
    14.4 Schrijver's Algorithm
    14.5 Symmetric Submodular Functions
    14.6 Submodular Function Maximization
    Exercises
    References
    15 NP-Completeness
    15.1 Turing Machines
    15.2 Church's Thesis
    15.3 P and NP
    15.4 Cook's Theorem
    15.5 Some Basic NP-Complete Problems
    15.6 The Class coNP
    15.7 NP-Hard Problems
    Exercises
    References
    16 Approximation Algorithms
    16.1 Set Covering
    16.2 The Max-Cut Problem
    16.3 Colouring
    16.4 Approximation Schemes
    16.5 Maximum Satisfiability
    16.6 The PCP Theorem
    16.7 L-Reductions
    Exercises
    References
    17 The Knapsack Problem
    17.1 Fractional Knapsack and Weighted Median Problem
    17.2 A Pseudopolynomial Algorithm
    17.3 A Fully Polynomial Approximation Scheme
    17.4 Multi-Dimensional Knapsack
    17.5 The Nemhauser-Ullmann Algorithm
    Exercises
    References
    18 Bin-Packing
    18.1 Greedy Heuristics
    18.2 An Asymptotic Approximation Scheme
    18.3 The Karmarkar-Karp Algorithm
    Exercises
    References
    19 Multicommodity Flows and Edge-Disjoint Paths
    19.1 Multicommodity Flows
    19.2 Algorithms for Multicommodity Flows
    19.3 Sparsest Cut and Max-Flow Min-Cut Ratio
    19.4 The Leighton-Rao Theorem
    19.5 Directed Edge-Disjoint Paths Problem
    19.6 Undirected Edge-Disjoint Paths Problem
    Exercises
    References
    20 Network Design Problems
    20.1 Steiner Trees
    20.2 The Robins-Zelikovsky Algorithm
    20.3 Rounding the Directed Component LP
    20.4 Survivable Network Design
    20.5 A Primal-Dual Approximation Algorithm
    20.6 Jain's Algorithm
    20.7 The VPN Problem
    Exercises
    References
    21 The Traveling Salesman Problem
    21.1 Approximation Algorithms for the TSP
    21.2 Euclidean TSP
    21.3 Local Search
    21.4 The Traveling Salesman Polytope
    21.5 Lower Bounds
    21.6 Branch-and-Bound
    Exercises
    References
    22 Facility Location
    22.1 The Uncapacitated Facility Location Problem
    22.2 Rounding Linear Programming Solutions
    22.3 Primal-Dual Algorithms
    22.4 Scaling and Greedy Augmentation
    22.5 Bounding the Number of Facilities
    22.6 Local Search
    22.7 Capacitated Facility Location Problems
    22.8 Universal Facility Location
    Exercises
    References
    Notation Index
    Author Index
    Subject Index
    Algorithms and Combinatorics 21 BernhardKorte JensVygen Combinatorial Optimization Theory and Algorithms Sixth Edition
    Algorithms and Combinatorics Volume 21 Editorial Board William J. Cook Ronald Graham Bernhard Korte László Lovász Avi Wigderson Günter M. Ziegler
    More information about this series at http://www.springer.com/series/13
    Bernhard Korte • Jens Vygen Combinatorial Optimization Theory and Algorithms Sixth Edition 123
    Bernhard Korte Research Institute for Discrete Mathematics University of Bonn Bonn, Germany Jens Vygen Research Institute for Discrete Mathematics University of Bonn Bonn, Germany ISSN 0937-5511 Algorithms and Combinatorics ISBN 978-3-662-56038-9 https://doi.org/10.1007/978-3-662-56039-6 ISSN 2197-6783 (electronic) ISBN 978-3-662-56039-6 (eBook) Library of Congress Control Number: 2017958030 Mathematics Subject Classification (2010): 90C27, 68R10, 05C85, 68Q25 © Springer-Verlag GmbH Germany 2000, 2002, 2006, 2008, 2012, 2018 This work is subject to copyright. All rights are reserved by the Publisher, 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 physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, 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. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. trademarks, service marks, etc. Printed on acid-free paper This Springer imprint is published by Springer Nature The registered company is Springer-Verlag GmbH, DE The registered company address is: Heidelberger Platz 3, 14197 Berlin, Germany
    Preface to the Sixth Edition After six years, it was again time for a new edition. Besides updates, new exercises, and a few corrections, it contains the following new material. Section 7.4 is devoted to shallow-light trees. Section 14.6 contains the recent two-factor approximation algorithm for submodular function maximization. Sec- tion 17.5 discusses the Nemhauser-Ullmann algorithm and smoothed analysis. In Section 20.3, we present the (ln 4 + )-factor approximation algorithm for the Steiner tree problem. Finally, Section 20.7 contains the VPN theorem. There are also small additions, e.g. on the integrality ratio in Section 5.1 and kernelization in Section 15.7. We would like to thank Maxim Babenko, Steffen Böhmer, Ulrich Brenner, György Dósa, Michael Etscheid, Jean Fonlupt, Michel Goemans, Stephan Held, Stefan Hougardy, Jochen Könemann, Solomon Lo, Jens Maßberg, Neil Olver, Dieter Rautenbach, Heiko Röglin, Jan Schneider, Sophie Spirkl, and Uri Zwick for feedback on the previous edition or proofreading new parts. We hope that, with this new edition, the book remains useful for research and teaching for many years to come. Bonn, Germany September 2017 Bernhard Korte Jens Vygen V
    Preface to the Fifth Edition When preparing the first edition of this book, more than 10 years ago, we tried to accomplish two objectives: it should be useful as an advanced graduate textbook but also as a reference work for research. With each new edition, we have to decide how the book can be improved further. Of course, it is less and less possible to describe the growing area comprehensively. If we included everything that we like, the book would grow beyond a single volume. Since the book is used for many courses, now even sometimes at un- dergraduate level, we thought that adding some classical material might be more useful than including a selection of the latest results. In this edition, we added a proof of Cayley’s formula, more details on blocking flows, the new faster b-matching separation algorithm, an approximation scheme for multidimensional knapsack, and results concerning the multicommodity max-flow min-cut ratio and the sparsest cut problem. There are further small improvements in numerous places and more than 60 new exercises. Of course, we also updated the references to point to the most recent results and corrected some minor errors that were discovered. We would like to thank Takao Asano, Maxim Babenko, Ulrich Brenner, Ben- jamin Bolten, Christoph Buchheim, Jean Fonlupt, András Frank, Michael Gester, Stephan Held, Stefan Hougardy, Hiroshi Iida, Klaus Jansen, Alexander Karzanov, Levin Keller, Alexander Kleff, Niko Klewinghaus, Stefan Knauf, Barbara Langfeld, Jens Maßberg, Marc Pfetsch, Klaus Radke, Rabe von Randow, Tomás Salles, Jan Schneider, Christian Schulte, András Seb˝o, Martin Skutella, Jácint Szabó, and Simon Wedeking for valuable feedback on the previous edition. We are pleased that this book has been received so well, and further translations are on their way. Editions in Japanese, French, Italian, German, Russian, and Chinese have appeared since 2009 or are scheduled to appear soon. We hope that our book will continue to serve its purpose in teaching and research in combinatorial optimization. Bonn, Germany September 2011 Bernhard Korte Jens Vygen VII
    Preface to the Fourth Edition With four English editions, and translations into four other languages forthcoming, we are very happy with the development of our book. Again, we have revised, updated, and significantly extended it for this fourth edition. We have added some classical material that may have been missed so far, in particular on linear pro- gramming, the network simplex algorithm, and the max-cut problem. We have also added a number of new exercises and up-to-date references. We hope that these changes serve to make our book an even better basis for teaching and research. We gratefully acknowledge the continuous support of the Union of the German Academies of Sciences and Humanities and the North Rhine-Westphalian (NRW) Academy of Sciences via the long-term research project “Discrete Mathematics and Its Applications.” We also thank those who gave us feedback on the third edition, in particular Takao Asano, Christoph Bartoschek, Bert Besser, Ulrich Brenner, Jean Fonlupt, Satoru Fujishige, Marek Karpinski, Jens Maßberg, Denis Naddef, Sven Peyer, Klaus Radke, Rabe von Randow, Dieter Rautenbach, Martin Skutella, Markus Struzyna, Jürgen Werber, Minyi Yue, and Guochuan Zhang, for their valuable comments. At http://www.or.uni-bonn.de/∼vygen/co.html, we will continue to maintain updated information about this book. Bonn, Germany August 2007 Bernhard Korte Jens Vygen IX
    分享到：
    赞 收藏

    相关推荐

    资料库

    行业

    共收录7266份资料，累计15个分类，关注成员有19位，主要包括：物流,旅游,餐饮零售,网络游戏,咨询,金融,电子政务,外包,教育,制造,医疗,嵌入式,互联网,交通,电信

    热门标签

    物流 旅游 餐饮零售 网络游戏 咨询 金融 电子政务 外包 教育 制造 医疗 嵌入式 互联网 交通 电信

    最新资料