Handbook of Combinatorial Optimization

Front Cover
Springer Science & Business Media, Dec 1, 2013 - Mathematics - 2406 pages
Combinatorial (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

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
Connections between Nonlinear Programming
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
Subject Index of Volumes 13
845
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information