## Combinatorial Optimization: Papers from the DIMACS Special YearWilliam Cook, László Lovász, Paul D. Seymour This is a carefully refereed collection of invited survey articles written by outstanding researchers. Aimed at researchers in discrete mathematics, operations research, and the theory of computing, this book offers an in-depth look at many topics not treated in textbooks. |

### What people are saying - Write a review

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

### Contents

Practical problem solving with cutting plane algorithms | 111 |

Michael Junger Gerhard Reinelt and Stefan Thienel | 153 |

Maximum cuts and largest bipartite subgraphs | 181 |

Algorithms and reformulations for lot sizing problems | 245 |

Efficient algorithms for disjoint paths in planar graphs | 295 |

Computing nearoptimal solutions to combinatorial optimization problems | 355 |

A survey | 399 |

### Common terms and phrases

affine approximation algorithm bipartite subgraph branch and bound branch and cut combinatorial optimization combinatorial optimization problems complete graph computation connected consider constraints contains convex corresponding cost cut node cut polytope cycle defined Delaunay polytope denote distance space dual eigenvalue entropy extreme Delaunay polytopes face boundary facet feasible solution flow formulation given graph entropy graph G grid graphs Grotschel Hence heuristic hypergraph hypermetric cone hypermetric inequalities hypermetric space induced subgraph instance integer programming Lemma Let G linear programming lot-sizing Lovasz lower bound Math matrix max-cut max-cut problem maximum mc(G metric minimal minimum multicommodity objective function obtain optimum pair path packing paths problem planar graphs Poljak polyhedral polynomial proof Proposition radius random Reinelt relaxation result root lattice satisfies Section simplex solvable solved sphere subproblem subset symmetric terminals Theorem traveling salesman problem upper bound valid inequalities variables vectors vertex set vertex-disjoint paths vertices weight