Handbook of Combinatorial Optimization

1. Front Matter

   Pages i-xxiv

   PDF

2. Mixed-Integer Nonlinear Optimization in Process Synthesis

   • C. S. Adjiman, C. A. Schweiger, C. A. Floudas

   Pages 1-76

3. Approximate Algorithms and Heuristics for MAX-SAT

   • Roberto Battiti, Marco Protasi

   Pages 77-148

4. Connections between Nonlinear Programming and Discrete Optimization

   • Franco Giannessi, Fabio Tardella

   Pages 149-188

5. Interior Point Methods for Combinatorial Optimization

   • John E. Mitchell, Panos M. Pardalos, Mauricio G. C. Resende

   Pages 189-297

6. Knapsack Problems

   • David Pisinger, Paolo Toth

   Pages 299-428

7. Fractional Combinatorial Optimization

   • Tomasz Radzik

   Pages 429-478

8. Reformulation-Linearization Techniques for Discrete Optimization Problems

   • Hanif D. Sherali, Warren P. Adams

   Pages 479-532

9. Gröbner Bases in Integer Programming

   • Rekha R. Thomas

   Pages 533-572

10. Applications of Set Covering, Set Packing and Set Partitioning Models: A Survey

    • R. R. Vemuganti

    Pages 573-746

11. Efficient Algorithms for Geometric Shortest Path Query Problems

    • Danny Z. Chen

    Pages 747-779

12. Computing Distances between Evolutionary Trees

    • Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Lusheng Wang et al.

    Pages 781-822

13. Combinatorial Optimization and Coalition Games

    • Xiaotie Deng

    Pages 823-849

14. Steiner Minimal Trees: An Introduction, Parallel Computation, and Future Work

    • Frederick C. Harris Jr.

    Pages 851-903

15. Resource Allocation Problems

    • Naoki Katoh, Toshihide Ibaraki

    Pages 905-1006

16. Combinatoral Optimization in Clustering

    • Boris Mirkin, Ilya Muchnik

    Pages 1007-1075

17. The Graph Coloring Problem: A Bibliographic Survey

    • Panos M. Pardalos, Thelma Mavridou, Jue Xue

    Pages 1077-1141

18. Steiner Minimal Trees in E ³: Theory, Algorithms, and Applications

    • J. MacGregor Smith

    Pages 1143-1216

19. Dynamical System Approaches to Combinatorial Optimization

    • Jens Starke, Michael Schanz

    Pages 1217-1270

20. On-line Dominating Set Problems for Graphs

    • Wen-Guey Tzeng

    Pages 1271-1288

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. dualheuristics).

• algorithms
• artificial intelligence
• combinatorial optimization
• communication
• dynamical systems
• graph theory
• heuristics
• linear optimization
• network
• nonlinear optimization
• number theory
• operations research
• optimization
• programming
• statistics
• combinatorics
• information and communication, circuits

• University of Minnesota, Minneapolis, USA

  Ding-Zhu Du

• University of Florida, Gainesville, USA

  Panos M. Pardalos

Policies and ethics