Paradigms of Combinatorial Optimization: Problems and New Approaches

Cover

Paradigms of Combinatorial Optimization - Problems and New Approaches

ISBN 9781848211483

Table of Contents

Preface

PART I Paradigmatic Problems

Chapter 1 Optimal Satisfibility
1.1. Introduction
1.2. Preliminaries
o 1.2.1. Constraint satisfaction problems: decision and optimization versions
o 1.2.2. Constraint types
1.3. Complexity of decision problems
1.4. Complexity and approximation of optimization problems
o 1.4.1. Maximization problems
o 1.4.2. Minimization problems
1.5. Particular instances of constraint satisfaction problems
o 1.5.1. Planar instances
o 1.5.2. Dense instances
o 1.5.3. Instances with a bounded number of occurrences
1.6. Satisfability problems under global constraints
1.7. Conclusion
1.8. Bibliography
Chapter 2 Scheduling Problems
2.1. Introduction
2.2. New techniques for approximation
o 2.2.1. Linear programming and scheduling
o 2.2.2. An approximation scheme for P||Cmax
2.3. Constraints and scheduling
o 2.3.1. The monomachine constraint
o 2.3.2. The cumulative constraint
o 2.3.3. Energetic reasoning
2.4. Non-regular criteria
o 2.4.1. PERT with convex costs
o 2.4.2. Minimizing the early-tardy cost on one machine
2.5. Bibliography
Chapter 3 Location Problems
3.1. Introduction
o 3.1.1. Weber's problem
o 3.1.2. A classifcation
3.2. Continuous problems
o 3.2.1. Complete covering
o 3.2.2. Maximal covering
o 3.2.3. Empty covering
o 3.2.4. Bicriteria models
o 3.2.5. Covering with multiple resources
3.3. Discrete problems
o 3.3.1. p-Center
o 3.3.2. p-Dispersion
o 3.3.3. p-Median
o 3.3.4. Hub
o 3.3.5. p-Maxisum
3.4. On-line problems
3.5. The quadratic assignment problem
o 3.5.1. Defnitions and formulations of the problem
o 3.5.2. Complexity
o 3.5.3. Relaxations and lower bounds
3.6. Conclusion
3.7. Bibliography
Chapter 4 MiniMax Algorithms and Games
4.1. Introduction
4.2. Games of no chance: the simple cases
4.3. The case of complex no chance games
o 4.3.1. Approximative evaluation
o 4.3.2. Horizon effect
o 4.3.3. a- pruning
4.4. Quiescence search
o 4.4.1. Other refnements of the MiniMax algorithm
4.5. Case of games using chance
4.6. Conclusion
4.7. Bibliography
Chapter 5 Two-dimensional Bin Packing Problems
5.1. Introduction
5.2. Models
o 5.2.1. ILP models for level packing
5.3. Upper bounds
o 5.3.1. Strip packing
o 5.3.2. Bin packing: two-phase heuristics
o 5.3.3. Bin packing: one-phase level heuristics
o 5.3.4. Bin packing: one-phase non-level heuristics
o 5.3.5. Metaheuristics
o 5.3.6. Approximation algorithms
5.4. Lower bounds
o 5.4.1. Lower bounds for level packing
5.5. Exact algorithms
5.6. Acknowledgments
5.7. Bibliography
Chapter 6 The Maximum Cut Problem
6.1. Introduction
6.2. Complexity and polynomial cases
6.3. Applications
o 6.3.1. Spin glass models
o 6.3.2. Unconstrained 0-1 quadratic programming
o 6.3.3. The via minimization problem
6.4. The cut polytope
o 6.4.1. Valid inequalities and separation
o 6.4.2. Branch-and-cut algorithms
o 6.4.3. The cut polyhedron
6.5. Semi-defnite programming (SDP) and the maximum cut problem
o 6.5.1. Semi-defnite formulation of the MAX-CUT problem
o 6.5.2. Quality of the semi-defnite formulation
o 6.5.3. Existing works in the literature
6.6. The cut cone and applications
o 6.6.1. The cut cone
o 6.6.2. Relationship to the cut polytope
o 6.6.3. The semi-metric cone
o 6.6.4. Applications to the multifow problem
6.7. Approximation methods
o 6.7.1. Methods with performance guarantees
o 6.7.2. Methods with no guarantees
6.8. Related problems
o 6.8.1. Unconstrained 0-1 quadratic programming
o 6.8.2. The maximum even (odd) cut problem
o 6.8.3. The equipartition problem
o 6.8.4. Other problems
6.9. Conclusion
6.10. Bibliography
Chapter 7 The Traveling Salesman Problem and its Variations
7.1. Introduction
7.2. Elementary properties and various subproblems
o 7.2.1. Elementary properties
o 7.2.2. Various subproblems
7.3. Exact solving algorithms
o 7.3.1. A dynamic programming algorithm
o 7.3.2. A branch-and-bound algorithm
7.4. Approximation algorithm for max TSP
o 7.4.1. An algorithm based on 2-matching
o 7.4.2. Algorithm mixing 2-matching and matching
7.5. Approximation algorithm for min TSP
o 7.5.1. Algorithm based on the spanning tree and matching
o 7.5.2. Local search algorithm
7.6. Constructive algorithms
o 7.6.1. Nearest neighbor algorithm
o 7.6.2. Nearest insertion algorithm
7.7. Conclusion
7.8. Bibliography
Chapter 8 0-1 Knapsack Problems
8.1. General solution principle
8.2. Relaxation
8.3. Heuristic
8.4. Variable fxing
8.5. Dynamic programming
o 8.5.1. General principle
o 8.5.2. Managing feasible combinations of objects
8.6. Solution search by hybridization of branch-and-bound and dynamic
o 8.6.1. Principle of hybridization
o 8.6.2. Illustration of hybridization
8.7. Conclusion
8.8. Bibliography
Chapter 9 Integer Quadratic Knapsack Problems
9.1. Introduction
o 9.1.1. Problem formulation
o 9.1.2. Signifcance of the problem
9.2. Solution methods
o 9.2.1. The convex separable problem
o 9.2.2. The non-convex separable problem
o 9.2.3. The convex non-separable problem
o 9.2.4. The non-convex non-separable problem
9.3. Numerical experiments
o 9.3.1. The convex and separable integer quadratic knapsack problem
o 9.3.2. The convex and separable integer quadratic multi-knapsack problem
9.4. Conclusion
9.5. Bibliography
Chapter 10 Graph Coloring Problems
10.1. Basic notions of colorings
10.2. Complexity of coloring
10.3. Sequential methods of coloring
10.4. An exact coloring algorithm
10.5. Tabu search
10.6. Perfect graphs
10.7. Chromatic scheduling
10.8. Interval coloring
10.9. T -colorings
10.10. List colorings
10.11. Coloring with cardinality constraints
10.12. Other extensions
10.13. Edge coloring
o 10.13.1. f -Coloring of edges
o 10.13.2. [g, f]-Colorings of edges
o 10.13.3. A model of hypergraph coloring
10.14. Conclusion
10.15. Bibliography

PART II New Approaches

Chapter 11 Polynomial Approximation
11.1. What is polynomial approximation?
o 11.1.1. Effciently solving a diffcult problem
o 11.1.2. Approximation measures
11.2. Some frst examples of analysis: constant approximation ratios
o 11.2.1. An example of classical approximation: the metric traveling salesman
o 11.2.2. Examples of the differential ratio case
11.3. Approximation schemes
o 11.3.1. Non-complete schemes
o 11.3.2. Complete approximation schemes - example of the Boolean knapsack
11.4. Analyses depending on the instance
o 11.4.1. Set covering and classical ratios
o 11.4.2. Set covering and differential ratios
o 11.4.3. The maximum stable set problem
11.5. Conclusion: methods and issues of approximation
o 11.5.1. The types of algorithms: a few great classics
o 11.5.2. Approximation classes: structuring the class NPO
o 11.5.3. Reductions in approximation
o 11.5.4. Issues
11.6. Bibliography
Chapter 12 Approximation Preserving Reductions
12.1. Introduction
12.2. Strict and continuous reductions
o 12.2.1. Strict reductions
o 12.2.2. Continuous reduction
12.3. AP-reduction and completeness in the classes NPO and APX
o 12.3.1. Completeness in NPO
o 12.3.2. Completeness in APX
o 12.3.3. Using completeness to derive negative results
12.4. L-reduction and completeness in the classes Max-SNP and APX
o 12.4.1. The L-reduction and the class Max-SNP
o 12.4.2. Examples of L-reductions
o 12.4.3. Completeness in Max-SNP and APX
12.5. Affne reduction
12.6. A few words on GAP-reduction
12.7. History and comments
12.8. Bibliography
Chapter 13 Inapproximability of Combinatorial Optimization Problems
13.1. Introduction
o 13.1.1. A brief historical overview
o 13.1.2. Organization of this chapter
o 13.1.3. Further reading
13.2. Some technical preliminaries
13.3. Probabilistically checkable proofs
o 13.3.1. PCP and the approximability of Max SAT
13.4. Basic reductions
o 13.4.1. Max 3SAT with bounded occurrences
o 13.4.2. Vertex Cover and Independent Set
o 13.4.3. Steiner tree problem
o 13.4.4. More about Independent Set
13.5. Optimized reductions and PCP constructions
o 13.5.1. PCPs optimized for Max SAT and Max CUT
o 13.5.2. PCPs optimized for Independent Set
o 13.5.3. The Unique Games Conjecture
13.6. An overview of known inapproximability results
o 13.6.1. Lattice problems
o 13.6.2. Decoding linear error-correcting codes
o 13.6.3. The traveling salesman problem
o 13.6.4. Coloring problems
o 13.6.5. Covering problems
o 13.6.6. Graph partitioning problems
13.7. Integrality gap results
o 13.7.1. Convex relaxations of the Sparsest Cut problem
o 13.7.2. Families of relaxations
o 13.7.3. Integrality gaps versus Unique Games
13.8. Other topics
o 13.8.1. Complexity classes of optimization problems
o 13.8.2. Average-case complexity and approximability
o 13.8.3. Witness length in PCP constructions
o 13.8.4. Typical and unusual approximation factors
13.9. Conclusions
13.10. Prove optimal results for 2-query PCPs
13.11. Settle the Unique Games Conjecture
13.12. Prove a strong inapproximability result for Metric TSP
13.13. Acknowledgements
13.14. Bibliography
Chapter 14 Local Search: Complexity and Approximation
14.1. Introduction
14.2. Formal framework
14.3. A few familiar optimization problems and their neighborhoods
o 14.3.1. Graph partitioning problem
o 14.3.2. The maximum cut problem
o 14.3.3. The traveling salesman problem
o 14.3.4. Clause satisfaction problems
o 14.3.5. Stable confgurations in a Hopfeld-type neural network
14.4. The PLS class
14.5. Complexity of the standard local search algorithm
14.6. The quality of local optima
14.7. Approximation results
o 14.7.1. The MAX k-SAT problem
o 14.7.2. The MAX CUT problem
o 14.7.3. Other problems on graphs
o 14.7.4. The traveling salesman problem
o 14.7.5. The quadratic assignment problem
o 14.7.6. Classifcation problems
o 14.7.7. Facility location problems
14.8. Conclusion and open problems
14.9. Bibliography
Chapter 15 On-line Algorithms
15.1. Introduction
15.2. Some classical on-line problems
o 15.2.1. List updating
o 15.2.2. Paging
o 15.2.3. The traveling salesman problem
o 15.2.4. Load balancing
15.3. Competitive analysis of deterministic algorithms
o 15.3.1. Competitive analysis of list updating
o 15.3.2. Competitive analysis of paging algorithms
o 15.3.3. Competitive analysis of on-line TSP
o 15.3.4. Competitive analysis of on-line load balancing
15.4. Randomization
o 15.4.1. Randomized paging
o 15.4.2. Lower bounds: Yao's lemma and its application to paging algorithms
15.5. Extensions of competitive analysis
o 15.5.1. Ad hoc techniques: the case of paging
o 15.5.2. General techniques
15.6. Bibliography
Chapter 16 Polynomial Approximation for Multicriteria Combinatorial Optimization Problems
16.1. Introduction
16.2. Presentation of multicriteria combinatorial problems
o 16.2.1. Multicriteria combinatorial problems
o 16.2.2. Optimality
o 16.2.3. Complexity of multicriteria combinatorial problems
16.3. Polynomial approximation and performance guarantee
o 16.3.1. Criteria weighting approach
o 16.3.2. Simultaneous approach
o 16.3.3. Budget approach
o 16.3.4. Pareto curve approach
16.4. Bibliographical notes
o 16.4.1. Presentation of multicriteria combinatorial problems
o 16.4.2. Polynomial approximation with performance guarantees
16.5. Conclusion
16.6. Bibliography
Chapter 17 An Introduction to Inverse Combinatorial Problems
17.1. Introduction
17.2. Defnitions and notation
17.3. Polynomial inverse problems and solution techniques
o 17.3.1. The linear programming case
o 17.3.2. Inverse maximum fow problem
o 17.3.3. A class of polynomial inverse problems
o 17.3.4. Avenues to explore: the example of the inverse bivalent variable maximum
17.4. Hard inverse problems
o 17.4.1. Inverse NP-hard problems
o 17.4.2. Facility location problem
o 17.4.3. A partial inverse problem: the minimum capacity cut
o 17.4.4. Maximum weight matching problem
17.5. Conclusion
17.6. Bibliography
Chapter 18 Probabilistic Combinatorial Optimization
18.1. Motivations and applications
18.2. The issues: formalism and methodology
18.3. Problem complexity
o 18.3.1. Membership of NP is not given
o 18.3.2. Links between the deterministic and probabilistic frameworks from the
18.4. Solving problems
o 18.4.1. Characterization of optimal solutions
o 18.4.2. Polynomial solution of certain instances
o 18.4.3. Effective solution
18.5. Approximation
18.6. Bibliography
Chapter 19 Robust Shortest Path Problems
19.1. Introduction
19.2. Taking uncertainty into account: the various models
o 19.2.1. The interval model
o 19.2.2. The discrete scenario model
19.3. Measures of robustness
o 19.3.1. Classical criterion derived from decision-making theory
o 19.3.2. Methodology inspired by mathematical programming
o 19.3.3. Methodology inspired by multicriteria analysis
19.4. Complexity and solution of robust shortest path problems in the interval
o 19.4.1. With the worst-case criterion
o 19.4.2. With the maximum regret criterion
o 19.4.3. With the mathematical programming inspired approach
o 19.4.4. With the multicriteria analysis inspired approach
19.5. Complexity and solution of robust shortest path problems in a discrete set
o 19.5.1. With the worst-case criterion
o 19.5.2. With the maximum regret criterion
o 19.5.3. With the multicriteria analysis inspired approach
19.6. Conclusion
19.7. Bibliography
Chapter 20 Algorithmic Games
20.1. Preliminaries
o 20.1.1. Basic notions of games
o 20.1.2. The classes of complexity covered in this chapter
20.2. Nash equilibria
20.3. Mixed extension of a game and Nash equilibria
20.4. Algorithmic problems
o 20.4.1. Succinct description game
o 20.4.2. Results on the complexity of computing a mixed equilibrium
o 20.4.3. Counting the number of equilibria in a mixed strategy game
20.5. Potential games
o 20.5.1. Defnitions
o 20.5.2. Properties
20.6. Congestion games
o 20.6.1. Rosenthal's model
o 20.6.2. Complexity of congestion games (Rosenthal's model)
o 20.6.3. Other models
20.7. Final notes
20.8. Bibliography

List of Authors

Index

Summary of Volume 1 Concepts of Combinatorial Optimization

Summary of Volume 3 Applications of Combinatorial Optimization