Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
Cover
Title Page
Copyright
Preface
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 a bounded 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.1.1. Single machine problems
2.2.1.2. Problems with m machines
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.1.1. The equality graph and its blocks
2.4.1.2. Generic algorithm
2.4.1.3. Complexity of the generic algorithm
2.4.2. Minimizing the early–tardy cost on one machine
2.4.2.1. Special cases
2.4.2.2. The lower bound
2.4.2.3. The branch-and-bound algorithm
2.4.2.4. Lower bounds in a node of the search tree
2.4.2.5. Upper bound
2.4.2.6. Branching rule
2.4.2.7. Dominance rules
2.4.2.8. Experimental results
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.2.1. Fixed radius
3.2.2.2. Variable radius
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.3.1. Fixed charge
3.3.4. Hub
3.3.5. p-Maxisum
3.4. On-line problems
3.5. The quadratic assignment problem
3.5.1. Definitions and formulations of the problem
3.5.2. Complexity
3.5.3. Relaxations and lower bounds
3.5.3.1. Linear relaxations
2.3.5.3.2. Semi-definite relaxations
3.5.3.3. Convex quadratic relaxations
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
4.3.1. Approximative evaluation
4.3.2. Horizon effect
4.3.3. α-β pruning
4.4. Quiescence search
4.4.1. Other refinements 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
5.2.1. ILP models for level packing
5.3. Upper bounds
5.3.1. Strip packing
5.3.2. Bin packing: two-phase heuristics
5.3.3. Bin packing: one-phase level heuristics
5.3.4. Bin packing: one-phase non-level heuristics
5.3.5. Metaheuristics
5.3.6. Approximation algorithms
5.4. Lower bounds
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
6.3.1. Spin glass models
6.3.2. Unconstrained 0–1 quadratic programming
6.3.3. The via minimization problem
6.4. The cut polytope
6.4.1. Valid inequalities and separation
6.4.2. Branch-and-cut algorithms
6.4.3. The cut polyhedron
6.5. Semi-definite programming (SDP) and the maximum cut problem
6.5.1. Semi-definite formulation of the MAX-CUT problem
6.5.2. Quality of the semi-definite formulation
6.5.3. Existing works in the literature
6.6. The cut cone and applications
6.6.1. The cut cone
6.6.2. Relationship to the cut polytope
6.6.3. The semi-metric cone
6.6.4. Applications to the multiflow problem
6.7. Approximation methods
6.7.1. Methods with performance guarantees
6.7.2. Methods with no guarantees
6.8. Related problems
6.8.1. Unconstrained 0–1 quadratic programming
6.8.2. The maximum even (odd) cut problem
6.8.3. The equipartition problem
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
7.2.1. Elementary properties
7.2.2. Various subproblems
7.3. Exact solving algorithms
7.3.1. A dynamic programming algorithm
7.3.2. A branch-and-bound algorithm
7.4. Approximation algorithm for max TSP
7.4.1. An algorithm based on 2-matching
7.4.2. Algorithm mixing 2-matching and matching
7.5. Approximation algorithm for min TSP
7.5.1. Algorithm based on the spanning tree and matching
7.5.2. Local search algorithm
7.6. Constructive algorithms
7.6.1. Nearest neighbor algorithm
7.6.1.1. The general case
7.6.1.2. The metric case
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 fixing
8.5. Dynamic programming
8.5.1. General principle
8.5.2. Managing feasible combinations of objects
8.6. Solution search by hybridization of branch-and-bound and dynamic programming
8.6.1. Principle of hybridization
8.6.2. Illustration of hybridization
8.7. Conclusion
8.8. Bibliography
Chapter 9: Integer Quadratic Knapsack Problems
9.1. Introduction
9.1.1. Problem formulation
9.1.2. Significance of the problem
9.1.2.1. A task assignment problem
9.1.2.2. Portfolio management
9.2. Solution methods
9.2.1. The convex separable problem
9.2.1.1. Solving the continuous relaxation
9.2.1.2. Calculating a “good” quality bound
9.2.2. The non-convex separable problem
9.2.3. The convex non-separable problem
9.2.4. The non-convex non-separable problem
9.2.4.1. Special case: the 0–1 variable quadratic knapsack problem
9.3. Numerical experiments
9.3.1. The convex and separable integer quadratic knapsack problem
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
10.13.1. f-Coloring of edges
10.13.2. [g, f]-Colorings of edges
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?
11.1.1. Effciently solving a diffcult problem
11.1.2. Approximation measures
11.2. Some first examples of analysis: constant approximation ratios
11.2.1. An example of classical approximation: the metric traveling salesman
11.2.2. Examples of the differential ratio case
11.2.2.1. Bin packing
11.2.2.2. Minimum graph coloring
11.2.2.3. Polynomially bounded traveling salesman
11.3. Approximation schemes
11.3.1. Non-complete schemes
11.3.1.1. A scheduling problem with p processors for the classical ratio
11.3.1.2. The Euclidean traveling salesman problem
11.3.1.2.1. Phase 1
11.3.1.2.2. Phase 2
11.3.1.2.3. Phase 3
11.3.1.3. An example in the case of the differential ratio: return to BIN PACKING
11.3.2. Complete approximation schemes – example of the Boolean knapsack
11.3.2.1. A great classic: the positive case for the classical ratio
11.3.2.2. A generalization: using the differential ratio
11.4. Analyses depending on the instance
11.4.1. Set covering and classical ratios
11.4.2. Set covering and differential ratios
11.4.3. The maximum stable set problem
11.5. Conclusion: methods and issues of approximation
11.5.1. The types of algorithms: a few great classics
11.5.2. Approximation classes: structuring the class NPO
11.5.3. Reductions in approximation
11.5.4. Issues
11.6. Bibliography
Chapter 12: Approximation Preserving Reductions
12.1. Introduction
12.2. Strict and continuous reductions
12.2.1. Strict reductions
12.2.2. Continuous reduction
12.3. AP-reduction and completeness in the classes NPO and APX
12.3.1. Completeness in NPO
12.3.2. Completeness in APX
12.3.3. Using completeness to derive negative results
12.4. L-reduction and completeness in the classes Max-SNP and APX
12.4.1. The L-reduction and the class Max-SNP
12.4.2. Examples of L-reductions
12.4.2.1. MAX 2SAT and MIN 2SAT
12.4.2.2. MAX 3SAT and MAX 2SAT
12.4.2.3. MAX 2SAT and MAX ≠ 3SAT
12.4.3. Completeness in Max-SNP and APX
12.5. Affine 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
13.1.1. A brief historical overview
13.1.2. Organization of this chapter
13.1.3. Further reading
13.2. Some technical preliminaries
13.3. Probabilistically checkable proofs
13.3.1. PCP and the approximabiity of Max SAT
13.4. Basic reductions
13.4.1. Max 3SAT with bounded occurrences
13.4.2. Vertex Cover and Independent Set
13.4.3. Steiner tree problem
13.4.4. More about Independent Set
13.5. Optimized reductions and PCP constructions
13.5.1. PCPs optimizedfor Max SAT and Max CUT
13.5.2. PCPs optimized for Independent Set
13.5.3. The Unique Games Conjecture
13.6. An overview of known inapproximabiity results
13.6.1. Lattice problems
13.6.2. Decoding linear error-correcting codes
13.6.3. The traveling salesman problem
13.6.4. Coloring problems
13.6.5. Covering problems
13.6.6. Graph partitioning problems
13.7. Integrality gap results
13.7.1. Convex relaxations of the Sparsest Cut problem
13.7.2. Families of relaxations
13.7.3. Integrality gaps versus Unique Games
13.8. Other topics
13.8.1. Complexity classes of optimization problems
13.8.2. Average-case complexity and approximability
13.8.3. Witness length in PCP constructions
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 inapproximabiity 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
14.3.1. Graph partitioning problem
14.3.2. The maximum cut problem
14.3.3. The traveling salesman problem
14.3.4. Clause satisfaction problems
14.3.5. Stable configurations in a Hopfield-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
14.7.1. The MAX k-SAT problem
14.7.2. The MAX CUT problem
14.7.3. Other problems on graphs
14.7.4. The traveling salesman problem
14.7.5. The quadratic assignment problem
14.7.6. Classification problems
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
15.2.1. List updating
15.2.2. Paging
15.2.3. The traveling salesman problem
15.2.4. Load balancing
15.3. Competitive analysis of deterministic algorithms
15.3.1. Competitive analysis of list updating
15.3.2. Competitive analysis ofpaging algorithms
15.3.3. Competitive analysis of on-line TSP
15.3.4. Competitive analysis of on-line load balancing
15.4. Randomization
15.4.1. Randomized paging
15.4.2. Lower bounds: Yao’s lemma and its application to paging algorithms
15.5. Extensions of competitive analysis
15.5.1. Ad hoc techniques: the case ofpaging
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
16.2.1. Multicriteria combinatorial problems
16.2.2. Optimality
16.2.2.1. Hierarchical optimality
16.2.2.2. Minmax type optimality
16.2.2.3. Pareto optimality
16.2.3. Complexity of multicriteria combinatorial problems
16.2.3.1. NP-completeness
16.2.3.2. Intractability
16.3. Polynomial approximation and performance guarantee
16.3.1. Criteria weighting approach
16.3.2. Simultaneous approach
16.3.3. Budget approach
16.3.4. Pareto curve approach
16.3.4.1. The bicriteria traveling salesman problem
16.3.4.2. A scheduling problem with costs
16.3.4.3. General results
16.4. Bibliographical notes
16.4.1. Presentation of multicriteria combinatorial problems
16.4.1.1. Optimality
16.4.1.2. Complexity
16.4.2. Polynomial approximation with performance guarantees
16.4.2.1. Criteria weighting approach
16.4.2.2. Simultaneous approach
16.4.2.3. Budget approach
16.4.2.4. Pareto curve approach
16.5. Conclusion
16.6. Bibliography
Chapter 17: An Introduction to Inverse Combinatorial Problems
17.1. Introduction
17.2. Definitions and notation
17.3. Polynomial inverse problems and solution techniques
17.3.1. The linear programming case
17.3.1.1. Inverse optimal path problem
17.3.1.2. Inverse minimum capacity cut problem
17.3.2. Inverse maximum flow problem
17.3.3. A class of polynomial inverse problems
17.3.4. Avenues to explore: the example of the inverse bivalent variable maximum weight matching problem
17.4. Hard inverse problems
17.4.1. Inverse NP-hard problems
17.4.1.1. The example of the maximum weight stable set
17.4.1.2. A comment on the inverse maximum traveling salesman problem
17.4.2. Facility location problem
17.4.3. A partial inverse problem: the minimum capacity cut
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
18.3.1. Membership of NP is not given
18.3.2. Links between the deterministic and probabilistic frameworks from the complexity point of view
18.4. Solving problems
18.4.1. Characterization of optimal solutions
18.4.2. Polynomial solution of certain instances
18.4.2.1. For the probabilistic traveling salesman problem
18.4.2.2. For the probabilistic stable and vertex covering problems
18.4.2.3. For probabilistic longest path problems
18.4.2.4. For the probabilistic coloring problem
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
19.2.1. The interval model
19.2.2. The discrete scenario model
19.3. Measures of robustness
19.3.1. Classical criterion derivedfrom decision-making theory
19.3.1.1. Worst-case criteria
19.3.1.2. Maximum regret criterion
19.3.2. Methodology inspired by mathematical programming
19.3.3. Methodology inspired by multicriteria analysis
19.3.3.1. Performance vector associated with a path
19.3.3.2. Aggregation models for robustness
19.4. Complexity and solution of robust shortest path problems in the interval model
19.4.1. With the worst-case criterion
19.4.2. With the maximum regret criterion
19.4.2.1. Complexity
19.4.2.2. Solution
19.4.3. With the mathematical programming inspired approach
19.4.4. With the multicriteria analysis inspired approach
19.5. Complexity and solution of robust shortest path problems in a discrete set of scenarios model
19.5.1. With the worst-case criterion
19.5.1.1. Complexity
19.5.1.2. Solution
19.5.2. With the maximum regret criterion
19.5.3. With the multicriteria analysis inspired approach
19.6. Conclusion
19.7. Bibliography
Chapter 20: Algorithmic Games
20.1. Preliminaries
20.1.1. Basic notions of games
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
20.4.1. Succinct description game
20.4.2. Results on the complexity of computing a mixed equilibrium
20.4.3. Counting the number of equilibria in a mixed strategy game
20.5. Potential games
20.5.1. Definitions
20.5.2. Properties
20.6. Congestion games
20.6.1. Rosenthal’s model
20.6.2. Complexity of congestion games (Rosenthal’s model)
20.6.3. Other models
20.7. Final notes
20.8. Bibliography
List of Authors
Index
← Prev
Back
Next →
← Prev
Back
Next →