## Handbook of Combinatorial OptimizationCombinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied math ematics. Combinatorial optimization problems arise in various applications, including communications network design, VLSI design, machine vision, air line crew scheduling, corporate planning, computer-aided design and man ufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. Furthermore, combinatorial optimization problems occur in many diverse areas such as linear and integer programming, graph theory, artificial intelligence, and number theory. All these problems, when formulated mathematically as the minimization or maximization of a certain function defined on some domain, have a commonality of discreteness. Historically, combinatorial optimization starts with linear programming. Linear programming has an entire range of important applications including production planning and distribution, personnel assignment, finance, alloca tion of economic resources, circuit simulation, and control systems. Leonid Kantorovich and Tjalling Koopmans received the Nobel Prize (1975) for their work on the optimal allocation of resources. Two important discover ies, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These algo rithms have had a profound effect in combinatorial optimization. Many polynomial-time solvable combinatorial optimization problems are special cases of linear programming (e.g. matching and maximum flow). In addi tion, linear programming relaxations are often the basis for many approxi mation algorithms for solving NP-hard problems (e.g. dual heuristics). |

### What people are saying - Write a review

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

### Contents

41 | |

51 | |

71 | |

77 | |

79 | |

85 | |

A different MAXSAT problem and completeness results | 117 |

Memoryless Local Search Heuristics | 128 |

Optimization Approach in Process Synthesis | 2 |

Computing Distances between Evolutionary Trees 35 | 35 |

Combinatorial Optimization and Coalition Games 77 | 77 |

An Introduction | 105 |

Resource Allocation Problems 159 | 159 |

Combinatoral Optimization in Clustering 261 | 261 |

A Bibliographic Survey 331 | 331 |

ksC | 374 |

Experimental analysis and threshold effects | 136 |

149 | |

Connections between Nonlinear Programming | 150 |

Equivalence between Integer and Real Optimization | 157 |

Piecewise Concave Functions and Minimax | 168 |

Interior Point Methods for Combinatorial | 190 |

Interior Point Methods for Combinatorial Optimization | 191 |

Solution techniques | 202 |

Knapsack Problems | 299 |

Subsetsum Problem | 351 |

Multiplechoice Knapsack Problem | 364 |

Bounded Knapsack Problem | 382 |

Unbounded Knapsack Problem | 394 |

Multiple Knapsack Problem | 402 |

Conclusion and Future Trends | 417 |

Fractional Combinatorial Optimization | 429 |

Abstract | 459 |

ReformulationLinearization Techniques | 479 |

Knapsack Problems are the simplest MPhard problems in Combinatorial | 482 |

Gröbner Bases in Integer Programming | 533 |

Applications of Set Covering Set Packing | 573 |

Efficient Algorithms for Geometric | 1 |

Dynamical System Approaches | 471 |

Online Dominating Set Problems for Graphs 525 | 525 |

Optimization Problems in Optical Networks 543 | 543 |

Shortest Networks on Surfaces 589 | 589 |

Minimum Weight Triangulations 617 | 617 |

Optimization Applications in the Airline Industry 635 | 635 |

Semidefinite Relaxations Multivariate Normal | 2 |

Routing and Topology Embedding in Lightwave Networks 171 | 171 |

The Quadratic Assignment Problem 241 | 241 |

Algorithmic Aspects of Domination in Graphs 339 | 339 |

Selected Algorithmic Techniques for Parallel Optimization 407 | 407 |

Multispace Search for Combinatorial Optimization 457 | 457 |

The Equitable Coloring of Graphs 543 | 543 |

Randomized Parallel Algorithms | 567 |

Tabu Search 621 | 621 |

Author Index | 747 |

Subject Index | 773 |

Author Index 727 | 727 |

Subject Index 749 | 749 |

Subject Index 779 | 779 |

845 | |

### Other editions - View all

Handbook of Combinatorial Optimization: Supplement, Volume 1 Ding-Zhu Du,Panos M. Pardalos Limited preview - 1999 |

Handbook of Combinatorial Optimization: Supplement, Volume 1 Ding-Zhu Du,Panos M. Pardalos Limited preview - 2013 |

### Common terms and phrases

algorithm applications approach approximation approximation algorithm binary branch-and-bound clauses combinatorial optimization computational consider constraints convex hull core cost cutting plane data structure defined denote Discrete dynamic programming edge feasible solution formulation geometric given global Global Optimization graph Gröbner Gröbner basis Heuristic inequalities instances integer programming interior point interior point method iterations Journal of Operational Knapsack Problem Lemma linear programming Location Problem lower bound LP relaxation Management Science Mathematical Programming matrix maximum minimize minimum MINLP node nonlinear objective function obtained Operations Research optimal solution optimization problems Pardalos partition path query planar graphs polynomial polytope primal prob programming problems proof quadratic relaxation satisfies Section semidefinite programming sequence shortest path solved Steiner submodular subset Subset-sum techniques Theorem tion tree upper bound variables vector Vehicle Routing vertex vertices weight