Atnaujinkite slapukų nuostatas

Combinatorial Optimization: Theory and Algorithms 5th ed. 2012 [Kietas viršelis]

4.33/5 (19 ratings by Goodreads)
,
  • Formatas: Hardback, 660 pages, aukštis x plotis: 235x155 mm, weight: 1178 g, XX, 660 p., 1 Hardback
  • Serija: Algorithms and Combinatorics 21
  • Išleidimo metai: 13-Jan-2012
  • Leidėjas: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • ISBN-10: 3642244874
  • ISBN-13: 9783642244872
Kitos knygos pagal šią temą:
Combinatorial Optimization: Theory and Algorithms 5th ed. 2012Didesnis paveikslėlis
  • Formatas: Hardback, 660 pages, aukštis x plotis: 235x155 mm, weight: 1178 g, XX, 660 p., 1 Hardback
  • Serija: Algorithms and Combinatorics 21
  • Išleidimo metai: 13-Jan-2012
  • Leidėjas: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • ISBN-10: 3642244874
  • ISBN-13: 9783642244872
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9783642244872.html
Raktažodžiai:
This comprehensive textbook on combinatorial optimization emphasizes theoretical results and algorithms with provably good performance, in contrast to heuristics. The text contains complete but concise proofs, and also provides numerous exercises and references.

This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references. This fifth edition has again been updated, revised, and significantly extended, with more than 60 new exercises and new material on various topics, including Cayley's formula, blocking flows, faster b-matching separation, multidimensional knapsack, multicommodity max-flow min-cut ratio, and sparsest cut. Thus, this book represents the state of the art of combinatorial optimization.

Recenzijos

From the reviews of the fifth edition:

The book would be most suitable as a graduate text for a mathematics or computer science course. It offers a good number of exercises . This book excels at providing very up-to-date results that give an idea of the state of the art, but also makes it clear that this is still a very active area of research. Overall, it is a comprehensive and interesting text that manages to present both the most classical and the most recent ideas in the field. (Angele M. Hamel, ACM Computing Reviews, August, 2012)

This is the 5th edition of one of the standard books in combinatorial optimization. It is an excellent book covering everything from the basics up to the most advanced topics (graduate level and current research). It provides theoretical results, underlying ideas, algorithms and the needed basics in graph theory in a very nice, comprehensive way. `Combinatorial Optimization can easily serve as complete reference for current research and is state-of-the-art. In this new edition references have been updated and new exercises were added. (Sebastian Pokutta, Zentralblatt MATH, Vol. 1237, 2012)

1 Introduction
1(12)
1.1 Enumeration
2(3)
1.2 Running Time of Algorithms
5(3)
1.3 Linear Optimization Problems
8(1)
1.4 Sorting
9(4)
Exercises
11(1)
References
12(1)
2 Graphs
13(38)
2.1 Basic Definitions
13(4)
2.2 Trees, Circuits, and Cuts
17(7)
2.3 Connectivity
24(7)
2.4 Eulerian and Bipartite Graphs
31(3)
2.5 Planarity
34(7)
2.6 Planar Duality
41(10)
Exercises
43(4)
References
47(4)
3 Linear Programming
51(22)
3.1 Polyhedra
52(4)
3.2 The Simplex Algorithm
56(4)
3.3 Implementation of the Simplex Algorithm
60(3)
3.4 Duality
63(4)
3.5 Convex Hulls and Polytopes
67(6)
Exercises
68(2)
References
70(3)
4 Linear Programming Algorithms
73(28)
4.1 Size of Vertices and Faces
73(3)
4.2 Continued Fractions
76(3)
4.3 Gaussian Elimination
79(3)
4.4 The Ellipsoid Method
82(6)
4.5 Khachiyan's Theorem
88(2)
4.6 Separation and Optimization
90(11)
Exercises
97(2)
References
99(2)
5 Integer Programming
101(30)
5.1 The Integer Hull of a Polyhedron
103(4)
5.2 Unimodular Transformations
107(2)
5.3 Total Dual Integrality
109(3)
5.4 Totally Unimodular Matrices
112(5)
5.5 Cutting Planes
117(4)
5.6 Lagrangean Relaxation
121(10)
Exercises
123(4)
References
127(4)
6 Spanning Trees and Arborescences
131(26)
6.1 Minimum Spanning Trees
131(7)
6.2 Minimum Weight Arborescences
138(4)
6.3 Polyhedral Descriptions
142(3)
6.4 Packing Spanning Trees and Arborescences
145(12)
Exercises
148(5)
References
153(4)
7 Shortest Paths
157(16)
7.1 Shortest Paths From One Source
158(4)
7.2 Shortest Paths Between All Pairs of Vertices
162(3)
7.3 Minimum Mean Cycles
165(8)
Exercises
167(2)
References
169(4)
8 Network Flows
173(38)
8.1 Max-Flow-Min-Cut Theorem
174(4)
8.2 Menger's Theorem
178(2)
8.3 The Edmonds-Karp Algorithm
180(2)
8.4 Dinic's, Karzanov's, and Fujishige's Algorithm
182(4)
8.5 The Goldberg-Tarjan Algorithm
186(4)
8.6 Gomory-Hu Trees
190(6)
8.7 The Minimum Capacity of a Cut in an Undirected Graph
196(15)
Exercises
199(6)
References
205(6)
9 Minimum Cost Flows
211(30)
9.1 Problem Formulation
211(3)
9.2 An Optimality Criterion
214(2)
9.3 Minimum Mean Cycle-Cancelling Algorithm
216(3)
9.4 Successive Shortest Path Algorithm
219(4)
9.5 Orlin's Algorithm
223(4)
9.6 The Network Simplex Algorithm
227(4)
9.7 Flows Over Time
231(10)
Exercises
233(4)
References
237(4)
10 Maximum Matchings
241(32)
10.1 Bipartite Matching
242(2)
10.2 The Tutte Matrix
244(2)
10.3 Tutte's Theorem
246(3)
10.4 Ear-Decompositions of Factor-Critical Graphs
249(6)
10.5 Edmonds' Matching Algorithm
255(18)
Exercises
264(4)
References
268(5)
11 Weighted Matching
273(28)
11.1 The Assignment Problem
274(2)
11.2 Outline of the Weighted Matching Algorithm
276(3)
11.3 Implementation of the Weighted Matching Algorithm
279(13)
11.4 Postoptimality
292(1)
11.5 The Matching Polytope
293(8)
Exercises
296(2)
References
298(3)
12 b-Matchings and T-Joins
301(20)
12.1 b-Matchings
301(4)
12.2 Minimum Weight T-Joins
305(4)
12.3 T-Joins and T-Cuts
309(4)
12.4 The Padberg-Rao Theorem
313(8)
Exercises
315(3)
References
318(3)
13 Matroids
321(34)
13.1 Independence Systems and Matroids
321(4)
13.2 Other Matroid Axioms
325(4)
13.3 Duality
329(4)
13.4 The Greedy Algorithm
333(5)
13.5 Matroid Intersection
338(5)
13.6 Matroid Partitioning
343(2)
13.7 Weighted Matroid Intersection
345(10)
Exercises
349(2)
References
351(4)
14 Generalizations of Matroids
355(22)
14.1 Greedoids
355(4)
14.2 Polymatroids
359(4)
14.3 Minimizing Submodular Functions
363(2)
14.4 Schrijver's Algorithm
365(4)
14.5 Symmetric Submodular Functions
369(8)
Exercises
371(3)
References
374(3)
15 NP-Completeness
377(36)
15.1 Turing Machines
377(3)
15.2 Church's Thesis
380(5)
15.3 P and NP
385(4)
15.4 Cook's Theorem
389(3)
15.5 Some Basic NP-Complete Problems
392(8)
15.6 The Class coNP
400(2)
15.7 NP-Hard Problems
402(11)
Exercises
406(4)
References
410(3)
16 Approximation Algorithms
413(46)
16.1 Set Covering
414(5)
16.2 The Max-Cut Problem
419(6)
16.3 Colouring
425(8)
16.4 Approximation Schemes
433(2)
16.5 Maximum Satisfiability
435(5)
16.6 The PCP Theorem
440(4)
16.7 L-Reductions
444(15)
Exercises
450(4)
References
454(5)
17 The Knapsack Problem
459(12)
17.1 Fractional Knapsack and Weighted Median Problem
459(3)
17.2 A Pseudopolynomial Algorithm
462(2)
17.3 A Fully Polynomial Approximation Scheme
464(3)
17.4 Multi-Dimensional Knapsack
467(4)
Exercises
468(1)
References
469(2)
18 Bin-Packing
471(18)
18.1 Greedy Heuristics
471(6)
18.2 An Asymptotic Approximation Scheme
477(4)
18.3 The Karmarkar-Karp Algorithm
481(8)
Exercises
484(2)
References
486(3)
19 Multicommodity Flows and Edge-Disjoint Paths
489(32)
19.1 Multicommodity Flows
490(4)
19.2 Algorithms for Multicommodity Flows
494(5)
19.3 Sparsest Cut and Max-Flow Min-Cut Ratio
499(1)
19.4 The Leighton-Rao Theorem
500(3)
19.5 Directed Edge-Disjoint Paths Problem
503(4)
19.6 Undirected Edge-Disjoint Paths Problem
507(14)
Exercises
513(4)
References
517(4)
20 Network Design Problems
521(36)
20.1 Steiner Trees
522(5)
20.2 The Robins-Zelikovsky Algorithm
527(5)
20.3 Survivable Network Design
532(4)
20.4 A Primal-Dual Approximation Algorithm
536(8)
20.5 Jain's Algorithm
544(13)
Exercises
550(3)
References
553(4)
21 The Traveling Salesman Problem
557(36)
21.1 Approximation Algorithms for the TSP
557(5)
21.2 Euclidean TSP
562(7)
21.3 Local Search
569(6)
21.4 The Traveling Salesman Polytope
575(6)
21.5 Lower Bounds
581(3)
21.6 Branch-and-Bound
584(9)
Exercises
586(3)
References
589(4)
22 Facility Location
593(36)
22.1 The Uncapacitated Facility Location Problem
593(2)
22.2 Rounding Linear Programming Solutions
595(2)
22.3 Primal-Dual Algorithms
597(6)
22.4 Scaling and Greedy Augmentation
603(3)
22.5 Bounding the Number of Facilities
606(3)
22.6 Local Search
609(6)
22.7 Capacitated Facility Location Problems
615(3)
22.8 Universal Facility Location
618(11)
Exercises
624(2)
References
626(3)
Notation Index 629(4)
Author Index 633(12)
Subject Index 645