Combinatorial optimizationA complete, highly accessible introduction to one of today's most exciting areas of applied mathematics One of the youngest, most vital areas of applied mathematics, combinatorial optimization integrates techniques from combinatorics, linear programming, and the theory of algorithms. Because of its success in solving difficult problems in areas from telecommunications to VLSI, from product distribution to airline crew scheduling, the field has seen a ground swell of activity over the past decade. Combinatorial Optimization is an ideal introduction to this mathematical discipline for advanced undergraduates and graduate students of discrete mathematics, computer science, and operations research. Written by a team of recognized experts, the text offers a thorough, highly accessible treatment of both classical concepts and recent results. The topics include: * Network flow problems * Optimal matching * Integrality of polyhedra * Matroids * NP-completeness Featuring logical and consistent exposition, clear explanations of basic and advanced concepts, many real-world examples, and helpful, skill-building exercises, Combinatorial Optimization is certain to become the standard text in the field for many years to come. |
What people are saying - Write a review
We haven't found any reviews in the usual places.
Contents
Optimal Trees and Paths | 9 |
Maximum Flow Problems | 37 |
MinimumCost Flow Problems | 91 |
Copyright | |
6 other sections not shown
Other editions - View all
Common terms and phrases
6-matching arc vw augmenting path bipartite graph characteristic vector choose combinatorial common independent set compute constraints convex hull corresponding cost cutting-plane define deleting denote digraph digraph G dual solution edge-set example Exercise exists feasible solution Figure find a minimum finite follows Ford's Algorithm fx(v given graph G Greedy Algorithm implies inequality integral vectors iterations Kruskal's Algorithm Lemma Let G linear linear-programming problem lower bound matching algorithm matching of G matching problem matrix Matroid Intersection maximum flow problem maximum matching maximum-weight Minimize minimum cut minimum-cost flow problem Moreover node nodes of G nonnegative obtain odd circuit optimal solution optimal T-join optimal value pair perfect matching polyhedron polynomial polytope Primal-Dual Algorithm proof Proposition Prove pseudonode replace result s)-dipath satisfies shortest path problem solve spanning tree step subgraph subset Suppose Theorem tour traveling salesman problem tree solution undirected graph weight
Bibliographic information
| Title | Combinatorial optimization Volume 33 of Wiley-Interscience series in discrete mathematics and optimization A Wiley Interscience publication |
| Author | William Cook |
| Editor | William Cook |
| Edition | illustrated |
| Publisher | Wiley, 1998 |
| Original from | the University of Michigan |
| Digitized | Feb 5, 2010 |
| ISBN | 047155894X, 9780471558941 |
| Length | 355 pages |
| Subjects | › Combinatorial optimization Mathematics / Combinatorics Mathematics / Discrete Mathematics Mathematics / General Mathematics / Linear Programming |
| Export Citation | BiBTeX EndNote RefMan |