## Combinatorial Optimization: Theory and AlgorithmsThis well-written textbook on combinatorial optimization puts special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. The book contains complete (but concise) proofs, as well as many deep results, some of which have not appeared in any previous books. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

13 | |

Linear Programming | 49 |

Linear Programming Algorithms | 65 |

5 | 91 |

15 | 343 |

Network Design Problems | 467 |

The Traveling Salesman Problem | 501 |

Facility Location 537 | 536 |

573 | |

585 | |

### Other editions - View all

### Common terms and phrases

approximation algorithm approximation scheme arborescence augmenting path bipartite graph blossom bound capacities cardinality Chapter combinatorial optimization Computing connected components consider contains convex Corollary deﬁne deﬁnition digraph digraph G dual ear-decomposition edge Edmonds Eulerian Exercise exists feasible solution ﬁnd ﬁrst Flow Problem G V(G given graph G greedoid Hamiltonian circuit Hence implies incidence vectors induction inequality Input instance integral vector iteration Lemma Let G Linear Programming logn Lov´asz Mathematics matrix matroid max{cx maximal maximum Maximum Flow Problem Metric minimal Minimum Cost Flow Minimum Spanning Tree minimum weight nonnegative NP-complete NP-hard OPT(I optimization problems optimum solution oracle outer Paths Problem perfect matching planar graph polyhedron polynomial polynomial-time algorithm polytope Proof Proposition prove reachable running s-t-path satisﬁes Schrijver Section shortest path Shortest Path Problem solve spanning tree subgraph subset T-join Theorem tour undirected graph unimodular variables vertex cover vertices