Combinatorial OptimizationM. W. Padberg |
Contents
1 Weakly admissible transformations for solving algebraic assignment | 1 |
12 Dual integrality in bmatching problems W R Pulleyblank 176 | 13 |
A new approach to | 19 |
Copyright | |
8 other sections not shown
Common terms and phrases
anti-blocking assignment problem augmenting path average b-matching problem b₁ branching c₁ comb inequalities combinatorial optimization complete graph components conditional bounds convex cost coefficients cutting planes Dantzig defined denote disjunction dual linear program dual variables facets feasible solution fractional vertices Fulkerson greedy algorithm greedy solution Grötschel hence heuristic hypergraph independence system iterations k)-greedy algorithm linear programming linear relaxation lower bound Mathematical Programming matrix matroid minimum N₁ node weights number of cuts objective function obtained Operations Research optimal dual solution optimal solution optimum polyhedra polyhedron polytope PRIMAL procedure Proof satisfies Section set covering problem SGRAD solves P1 subgradient optimization subgraph subproblem subsets subtour elimination constraint symmetric travelling salesman Table Theorem tour length transportation problem travelling salesman problem upper bound upper plane valid inequality VALUE2 vector vertex W₁ W₂