Combinatorial Optimization: Algorithm and ComplexityChristos H. Papadimitriou and Kenneth Steiglitz have combined the theory of computational complexity developed by computer scientists, and the foundations of mathematical programming developed by the operations research community. This text will be useful to students with a wide range of backgrounds, including computer science, operations research, and electrical engineering. 
What people are saying  Write a review
User ratings
5 stars 
 
4 stars 
 
3 stars 
 
2 stars 
 
1 star 

Review: Combinatorial Optimization: Algorithms and Complexity
User Review  DJ  Goodreadsanother gem from Dover Read full review
Review: Combinatorial Optimization: Algorithms and Complexity
User Review  DJ  Goodreadsanother gem from Dover Read full review
Common terms and phrases
algorithm of Fig augmenting path auxiliary digraph basis bfs's bipartite matching blossom capacities Chapter clique column combinatorial optimization combinatorial optimization problem complete components Consider constraints construct convex corresponding cost cycle defined digraph Dijkstra's algorithm directed graph ellipsoid algorithm example feasible solution Figure finite FloydWarshall algorithm FordFulkerson algorithm formulation graph G greedy algorithm Hamilton circuit hence inequalities input integer linear programming iteration labeling algorithm Lemma linear programming matching problem matrix matroid maxflow problem maximum matching method mincost flow nodes nonnegative NPcomplete number of steps optimal solution partition pivot polynomialtime algorithm polytope primaldual algorithm Proof result satisfy sequence shortest path shortestpath problem shown in Fig simplex algorithm solve spanning tree stage Suppose tableau Theorem tour transformation Traveling Salesman Problem variables vector vertex vertices yes instance zero