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