Handbook of Combinatorial Optimization

1. Front Matter

   Pages i-vii

   PDF

2. Data Correcting Algorithms in Combinatorial Optimization

   • Diptesh Ghosh, Boris Goldengorin, Gerard Sierksma

   Pages 1-53

3. The Steiner Ratio of Banach-Minkowski spaces - A Survey

   • Dietmar Cieslik

   Pages 55-81

4. Probabilistic Verification and Non-Approximability

   • Mario Szegedy

   Pages 83-191

5. Steiner Trees in Industry

   • Xiuzhen Cheng, Yingshu Li, Ding-Zhu Du, Hung Q. Ngo

   Pages 193-216

6. Network-based Models and Algorithms in Data Mining and Knowledge Discovery

   • Vladimir Boginski, Panos M. Pardalos, Alkis Vazacopoulos

   Pages 217-258

7. The Generalized Assignment Problem and Extensions

   • Dolores Romero Morales, H. Edwin Romeijn

   Pages 259-311

8. Optimal Rectangular Partitions

   • Xiuzhen Cheng, Ding-Zhu Du, Joon-Mo Kim, Lu Ruan

   Pages 313-327

9. Connected Dominating Set in Sensor Networks and MANETs

   • Jeremy Blum, Min Ding, Andrew Thaeler, Xiuzhen Cheng

   Pages 329-369

10. Back Matter

    Pages 371-394

    PDF

Combinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied ma- ematics. Combinatorial optimization problems arise in various applications, including communications network design, VLSI design, machine vision, a- line crew scheduling, corporate planning, computer-aided design and m- 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, allo- 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 discov- ies, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These al- 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 ad- tion, linear programming relaxations are often the basis for many appro- mation algorithms for solving NP-hard problems (e.g. dual heuristics).

• Partition
• algorithm
• algorithms
• combinatorial optimization
• data mining
• model
• network
• networks
• optimization
• verification
• combinatorics

• University of Minnesota, Minneapolis

  Ding-Zhu Du

• University of Florida, Gainesville

  Panos M. Pardalos

Policies and ethics