Combinatorial Optimization: Papers from the DIMACS Special Year
William Cook, László Lovász, Paul D. Seymour
American Mathematical Soc., Jan 1, 1995 - Mathematics - 441 pages
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.
Practical problem solving with cutting plane algorithms
Michael Junger Gerhard Reinelt and Stefan Thienel
Maximum cuts and largest bipartite subgraphs
Algorithms and reformulations for lot sizing problems
Efficient algorithms for disjoint paths in planar graphs
Computing nearoptimal solutions to combinatorial optimization problems
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