Paradigms of combinatorial optimization /

Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim to cover a wide range of topics in this area. These to...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Άλλοι συγγραφείς: Paschos, Vangelis Th
Μορφή: Ηλ. βιβλίο
Γλώσσα:English
Έκδοση: London : ISTE, Ltd. ; 2014.
Hoboken : Wiley, 2014.
Έκδοση:2nd ed.
Σειρά:ISTE.
Θέματα:
Διαθέσιμο Online:Full Text via HEAL-Link
Πίνακας περιεχομένων:
  • 4.2. Games of no chance: the simple cases4.3. The case of complex no chance games; 4.3.1. Approximative evaluation; 4.3.2. Horizon effect; 4.3.3. [alpha]-[beta] 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.
  • Cover; Title Page; Copyright; Contents; 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 constraints1.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 PCmax; 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 algorithm2.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 covering3.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; 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.