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

Start Free Trial

No credit card required