Combinatorial Optimization: Algorithm and Complexity
Christos 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
We haven't found any reviews in the usual places.
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 Floyd-Warshall algorithm Ford-Fulkerson algorithm formulation graph G greedy algorithm Hamilton circuit hence inequalities input integer linear programming iteration labeling algorithm Lemma linear programming matching problem matrix matroid max-flow problem maximum matching method min-cost flow nodes nonnegative NP-complete number of steps optimal solution partition pivot polynomial-time algorithm polytope primal-dual algorithm Proof result satisfy sequence shortest path shortest-path 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