O'Reilly logo

Applications of Combinatorial Optimization, 2nd Edition by Vangelis Th. Paschos

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required