Combinatorial optimization. Theory and algorithms (Q5915386)

This book describes the most important ideas, theoretical results, algorithms in combinatorial optimization and covers an advanced graduate text which can also be used as an up-to-date reference work for current research. It starts by reviewing basic graph theory and proving those results in (integer) linear programming which are most relevant for combinatorial optimization. The book is organized into twenty chapters as follows: Graphs, Linear programming, Linear programming algorithms, Integer programming, Spanning trees and arborescences, Shortest paths, Network flows, Minimum cost flows, Maximum matchings, Weighted matching, \(b\)-matchings and \(T\)-joins, Matroids, Generalizations of matroids, NP-completeness, Approximation algorithms, The knapsack problem, Bin-packing, Multicommodity flows and edge-disjoint paths, Network design problems, The traveling salesman problem. Chapters 5-13 have polynomial-time algorithms, while most of the problems studied in chapters 14-20 are NP-hard, i.e. a polynomial-time algorithm is unlikely to exist. All results are accompanied by detailed proofs. At the end of each chapter there are a number of exercises containing additional results and applications of the material in that chapter. Each chapter ends with a list of references, incuding texts recommended for further study.