Applications of Combinatorial Optimization, 2nd Edition

Summary of Volume 2Paradigms of Combinatorial Optimization

PART I. PARADIGMATIC PROBLEMS

Chapter 1. Optimal Satisfiability

1.1. Introduction

1.2. Preliminaries

1.2.1. Constraint satisfaction problems: decision and optimization versions

1.2.2. Constraint types

1.3. Complexity of decision problems

1.4. Complexity and approximation of optimization problems

1.4.1. Maximization problems

1.4.2. Minimization problems

1.5. Particular instances of constraint satisfaction problems

1.5.1. Planar instances

1.5.2. Dense instances

1.5.3. Instances with abounded number of occurrences

1.6. Satisfiability problems under global constraints

1.7. Conclusion

1.8. Bibliography

Chapter 2. Scheduling Problems

2.1. Introduction

2.2. New techniques for approximation

2.2.1. Linear programming and scheduling

2.2.2. An approximation scheme for P||Cmax

2.3. Constraints and scheduling

2.3.1. The monomachine constraint

2.3.2. The cumulative constraint

2.3.3. Energetic reasoning

2.4. Non-regular criteria

2.4.1. PERT with convex costs

2.4.2. Minimizing the early–tardy cost on one machine

2.5. Bibliography

Chapter 3. Location Problems

3.1. Introduction

3.1.1. Weber’s problem

3.1.2. A classification

3.2. Continuous problems

3.2.1. Complete covering

3.2.2. Maximal covering

3.2.3. Empty covering

3.2.4. Bicriteria models

3.2.5. Covering with multiple resources

3.3. Discrete problems

3.3.1. p-Center

3.3.2. p-Dispersion

3.3.3. p-Median

3.3.4. Hub

3.3.5. p-Maximum

3.4. Online problems

3.5. The quadratic assignment problem ...