Combinatorial Optimization: Papers from the DIMACS Special YearWilliam Cook, László Lovász, Paul D. Seymour American Mathematical Soc., 01.01.1995 - 441 Seiten 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. |
Inhalt
Practical problem solving with cutting plane algorithms | 111 |
Randomized algorithms in combinatorial optimization | 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 |
Andere Ausgaben - Alle anzeigen
Combinatorial Optimization: Papers from the DIMACS Special Year William Cook,László Lovász,Paul D. Seymour Eingeschränkte Leseprobe - 1995 |
Häufige Begriffe und Wortgruppen
approximation algorithm bipartite graph bipartite subgraph branch and cut combinatorial optimization combinatorial optimization problems complete graph computation connected consider constraints convex corresponding cost cut node cut polytope cutting plane cycle defined Delaunay polytope denote disjoint distance space dual eigenvalue entropy Extreme Delaunay polytopes face boundary facet feasible solution flow formulation given graph entropy graph G grid graphs Grötschel Hence heuristic hypergraph hypermetric cone hypermetric inequalities hypermetric space HYPn+1 induced subgraph instance integer programming isometric Lemma Let G linear programming lot-sizing Lovász lower bound Math matrix max-cut max-cut problem maximum mc(G metric minimal minimum NP-complete objective function obtain optimum pair path packing paths problem planar graphs Poljak polyhedral polynomial proof Proposition radius random result root lattice satisfies Section solvable solved subproblem subset symmetric terminals Theorem traveling salesman problem upper bound valid inequalities variables vectors vertex set vertex-disjoint paths vertices weight