Applications of Combinatorial Optimization, 2nd Edition

Summary of Volume 1Concepts of Combinatorial Optimization

PART I. COMPLEXITY OF COMBINATORIAL OPTIMIZATION PROBLEMS

Chapter 1. Basic Concepts in Algorithms and Complexity Theory

1.1. Algorithmic complexity

1.2. Problem complexity

1.3. The classes P, NP and NPO

1.4. Karp and Turing reductions

1.5. NP-completeness

1.6. Two examples of NP-complete problems

1.6.1. MIN VERTEX COVER

1.6.2. MAX STABLE

1.7. A few words on strong and weak NP-completeness

1.8. A few other well-known complexity classes

1.9. Bibliography

Chapter 2. Randomized Complexity

2.1. Deterministic and probabilistic algorithms

2.1.1. Complexity of a Las Vegas algorithm

2.1.2. Probabilistic complexity of a problem

2.2. Lower bound technique

2.2.1. Definitions and notations

2.2.2. Minimax theorem

2.2.3. The Loomis lemma and the Yao principle

2.3. Elementary intersection problem

2.3.1. Upper bound

2.3.2. Lower bound

2.3.3. Probabilistic complexity

2.4. Conclusion

2.5 Bibliography

PART II. CLASSICAL SOLUTION METHODS

Chapter 3. Branch-and-Bound Methods

3.1. Introduction

3.2. Branch-and-bound method principles

3.2.1. Principle of separation

3.2.2. Pruning principles

3.2.3. Developing the tree

3.3. A detailed example: the binary knapsack problem

3.3.1. Calculating the initial bound

3.3.2. First principle of separation

3.3.3. Pruning without evaluation

3.3.4. Evaluation

3.3.5. Complete execution of the branch-and-bound method for finding only one optimal solution

3.3.6. First variant: finding all the optimal solutions

3.3.7. ...