Combinatorial Optimization: Theory and Algorithms / Edition 5
  • Combinatorial Optimization: Theory and Algorithms / Edition 5
  • Combinatorial Optimization: Theory and Algorithms / Edition 5

Combinatorial Optimization: Theory and Algorithms / Edition 5

by Bernhard Korte, Jens Vygen
     
 

ISBN-10: 3642244874

ISBN-13: 9783642244872

Pub. Date: 01/10/2012

Publisher: Springer Berlin Heidelberg

This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It has arisen as the basis of several courses on combinatorial optimization and more special topics at graduate level. It contains complete but concise proofs, also for many deep results,

…  See more details below

Overview

This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It has arisen as the basis of several courses on combinatorial optimization and more special topics at graduate level. It contains complete but concise proofs, also for many deep results, some of which did not appear in a textbook before. Many very recent topics are covered as well, and many references are provided. Thus this book represents the state of the art of combinatorial optimization.

This fourth edition is again significantly extended, most notably with new material on linear programming, the network simplex algorithm, and the max-cut problem. Many further additions and updates are included as well.

Product Details

ISBN-13:
9783642244872
Publisher:
Springer Berlin Heidelberg
Publication date:
01/10/2012
Series:
Algorithms and Combinatorics Series, #21
Edition description:
5th ed. 2012
Pages:
660
Product dimensions:
6.10(w) x 9.20(h) x 1.60(d)

Table of Contents

1 Introduction 1

1.1 Enumeration 2

1.2 Running Time of Algorithms 5

1.3 Linear Optimization Problems 8

1.4 Sorting 9

Exercises 11

References 12

2 Graphs 13

2.1 Basic Definitions 13

2.2 Trees, Circuits, and Cuts 17

2.3 Connectivity 24

2.4 Eulerian and Bipartite Graphs 30

2.5 Planarity 33

2.6 Planar Duality 40

Exercises 43

References 46

3 Linear Programming 49

3.1 Polyhedra 50

3.2 The Simplex Algorithm 54

3.3 Implementation of the Simplex Algorithm 57

3.4 Duality 60

3.5 Convex Hulls and Polytopes 64

Exercises 66

References 68

4 Linear Programming Algorithms 71

4.1 Size of Vertices and Faces 71

4.2 Continued Fractions 74

4.3 Gaussian Elimination 77

4.4 The Ellipsoid Method 80

4.5 Khachiyan's Theorem 86

4.6 Separation and Optimization 88

Exercises 95

References 96

5 Integer Programming 99

5.1 The Integer Hull of a Polyhedron 101

5.2 Unimodular Transformations 105

5.3 Total Dual Integrality 107

5.4 Totally Unimodular Matrices 110

5.5 Cutting Planes 115

5.6 Lagrangean Relaxation 119

Exercises 121

References 125

6 Spanning Trees and Arborescences 127

6.1 Minimum Spanning Trees 127

6.2 Minimum Weight Arborescences 133

6.3 Polyhedral Descriptions 137

6.4 Packing Spanning Trees and Arborescences 140

Exercises 144

References 147

7 Shortest Paths 151

7.1 Shortest Paths From One Source 152

7.2 Shortest Paths Between All Pairs of Vertices 156

7.3 Minimum Mean Cycles 159

Exercises 161

References 163

8 Network Flows 165

8.1 Max-How-Min-Cut Theorem 166

8.2 Menger's Theorem 170

8.3 The Edmonds-Karp Algorithm 172

8.4 Blocking Flows and Fujishige's Algorithm 174

8.5 The Goldberg-TarjanAlgorithm 176

8.6 Gomory-Hu Trees 180

8.7 The Minimum Capacity of a Cut in an Undirected Graph 186

Exercises 189

References 194

9 Minimum Cost Flows 199

9.1 Problem Formulation 199

9.2 An Optimality Criterion 201

9.3 Minimum Mean Cycle-Cancelling Algorithm 203

9.4 Successive Shortest Path Algorithm 207

9.5 Orlin's Algorithm 211

9.6 The Network Simplex Algorithm 214

9.7 Flows Over Time 218

Exercises 220

References 224

10 Maximum Matchings 227

10.1 Bipartite Matching 228

10.2 The Tutte Matrix 230

10.3 Tutte's Theorem 232

10.4 Ear-Decompositions of Factor-Critical Graphs 235

10.5 Edmonds' Matching Algorithm 241

Exercises 250

References 254

11 Weighted Matching 257

11.1 The Assignment Problem 258

11.2 Outline of the Weighted Matching Algorithm 259

11.3 Implementation of the Weighted Matching Algorithm 262

11.4 Postoptimality 276

11.5 The Matching Polytope 277

Exercises 280

References 282

12 b-Matchings and T-Joins 285

12.1 b-Matchings 285

12.2 Minimum Weight T-Joins 289

12.3 T-Joins and T-Cuts 293

12.4 The Padberg-Rao Theorem 296

Exercises 299

References 302

13 Matroids 305

13.1 Independence Systems and Matroids 305

13.2 Other Matroid Axioms 309

13.3 Duality 313

13.4 The Greedy Algorithm 317

13.5 Matroid Intersection 322

13.6 Matroid Partitioning 327

13.7 Weighted Matroid Intersection 329

Exercises 332

References 334

14 Generalizations of Matroids 337

14.1 Greedoids 337

14.2 Polymatroids 341

14.3 Minimizing Submodular Functions 345

14.4 Schrijver's Algorithm 347

14.5 Symmetric Submodular Functions 351

Exercises 353

References 355

15 AT-Completeness 359

15.1 Turing Machines 359

15.2 Church's Thesis 362

15.3 P and NP 367

15.4 Cook's Theorem 371

15.5 Some Basic NP-Complete Problems 375

15.6 The Class coNP 382

15.7 NP-Hard Problems 384

Exercises 387

References 391

16 Approximation Algorithms 393

16.1 Set Covering 394

16.2 The Max-Cut Problem 399

16.3 Colouring 405

16.4 Approximation Schemes 413

16.5 Maximum Satisfiability 415

16.6 The PCP Theorem 420

16.7 L-Reductions 424

Exercises 430

References 434

17 The Knapsack Problem 439

17.1 Fractional Knapsack and Weighted Median Problem 439

17.2 A Pseudopolynomial Algorithm 442

17.3 A Fully Polynomial Approximation Scheme 444

Exercises 447

References 447

18 Bin-Packing 449

18.1 Greedy Heuristics 449

18.2 An Asymptotic Approximation Scheme 455

18.3 The Karmarkar-Karp Algorithm 459

Exercises 462

References 464

19 Multicommodity Flows and Edge-Disjoint Paths 467

19.1 Multicommodity Flows 468

19.2 Algorithms for Multicommodity Flows 471

19.3 Directed Edge-Disjoint Paths Problem 476

19.4 Undirected Edge-Disjoint Paths Problem 479

Exercises 485

References 487

20 Network Design Problems 491

20.1 Steiner Trees 492

20.2 The Robins-Zelikovsky Algorithm 497

20.3 Survivable Network Design 502

20.4 A Primal-Dual Approximation Algorithm 505

20.5 Jain's Algorithm 514

Exercises 520

References 522

21 The Traveling Salesman Problem 527

21.1 Approximation Algorithms for the TSP 527

21.2 Euclidean TSP 532

21.3 Local Search 539

21.4 The Traveling Salesman Polytope 545

21.5 Lower Bounds 551

22.5 Branch-and-Bound 553

Exercises 556

References 559

22 Facility Location 563

22.1 The Uncapacitated Facility Location Problem 563

22.2 Rounding Linear Programming Solutions 565

22.3 Primal-Dual Algorithms 567

22.4 Scaling and Greedy Augmentation 573

22.5 Bounding the Number of Facilities 576

22.6 Local Search 579

22.7 Capacitated Facility Location Problems 585

22.8 Universal Facility Location 588

Exercises 594

References 596

Notation Index 599

Author Index 603

Subject Index 613

Read More

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >