Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Optimization methods for logical inference / / Vijay Chandru, John Hooker
| Optimization methods for logical inference / / Vijay Chandru, John Hooker |
| Autore | Chandru Vijay <1953-> |
| Pubbl/distr/stampa | New York, New York : , : John Wiley & Sons, Inc., , 1999 |
| Descrizione fisica | 1 online resource (386 p.) |
| Disciplina |
511.3
519.3 |
| Collana | Wiley-Interscience Series in Discrete Mathematics and Optimization |
| Soggetto topico |
Combinatorial optimization
Logic, Symbolic and mathematical |
| ISBN |
1-283-28263-1
9786613282637 1-118-03316-7 1-118-03141-5 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Optimization Methods for Logical Inference; Contents; Preface; 1 Introduction; 1.1 Logic and Mathematics: The Twain Shall Meet; 1.2 Inference Methods for Logic Models; 1.3 Logic Modeling Meets Mathematical Modeling; 1.4 The Difficulty of Inference; 2 Propositional Logic: Special Cases; 2.1 Basic Concepts of Propositional Logic; 2.1.1 Formulas; 2.1.2 Normal Forms; 2.1.3 Rules; 2.2 Integer Programming Models; 2.2.1 Optimization and Inference; 2.2.2 The Linear Programming Relaxation; 2.3 Horn Polytopes; 2.3.1 Horn Resolution; 2.3.2 The Integer Least Element of a Horn Polytope
2.3.3 Dual Integrality of Horn Polytopes2.4 Quadratic and Renamable Horn Systems; 2.4.1 Satisfiability of Quadratic Systems; 2.4.2 The Median Characteristic of Quadratic Systems; 2.4.3 Recognizing Renamable Horn Systems; 2.4.4 Q-Horn Propositions; 2.5 Nested Clause Systems; 2.5.1 Nested Propositions: Definition and Recognition; 2.5.2 Maximum Satisfiability of Nested Clause Systems; 2.5.3 Extended Nested Clause Systems; 2.6 Extended Horn Systems; 2.6.1 The Rounding Theorem; 2.6.2 Satisfiability of Extended Horn Systems; 2.6.3 Verifying Renamable Extended Horn Systems 2.6.4 The Unit Resolution Property2.6.5 Extended Horn Rule Bases; 2.7 Problems with Integral Polytopes; 2.7.1 Balanced Problems; 2.7.2 Integrality and Resolution; 2.8 Limited Backtracking; 2.8.1 Maximum Embedded Renamable Horn Systems; 2.8.2 Hierarchies of Satisfiability Problems; 2.8.3 Generalized and Split Horn Systems; 3 Propositional Logic: The General Case; 3.1 Two Classic Inference Methods; 3.1.1 Resolution for Propositional Logic; 3.1.2 A Simple Branching Procedure; 3.1.3 Branching Rules; 3.1.4 Implementation of a Branching Algorithm; 3.1.5 Incremental Satisfiability 3.2 Generating Hard Problems3.2.1 Pigeonhole Problems; 3.2.2 Problems Based on Graphs; 3.2.3 Random Problems Hard for Resolution; 3.2.4 Random Problems Hard for Branching; 3.3 Branching Methods; 3.3.1 Branch and Bound; 3.3.2 Jeroslow-Wang Method; 3.3.3 Horn Relaxation Method; 3.3.4 Bounded Resolution Method; 3.4 Tableau Methods; 3.4.1 The Simplex Method in Tableau Form; 3.4.2 Pivot and Complement; 3.4.3 Column Subtraction; 3.5 Cutting Plane Methods; 3.5.1 Resolvents as Cutting Planes; 3.5.2 Unit Resolution and Rank 1 Cuts; 3.5.3 A Separation Algorithm for Rank 1 Cuts 3.5.4 A Branch-and-Cut Algorithm3.5.5 Extended Resolution and Cutting Planes; 3.6 Resolution for 0-1 Inequalities; 3.6.1 Inequalities as Logical Formulas; 3.6.2 A Generalized Resolution Algorithm; 3.6.3 Some Examples; 3.7 A Set-Covering Formulation with Facet Cuts; 3.7.1 The Set-Covering Formulation; 3.7.2 Elementary Facets of Satisfiability; 3.7.3 Resolvent Facets Are Prime Implications; 3.7.4 A Lifting Technique for General Facets; 3.8 A Nonlinear Programming Approach; 3.8.1 Formulation as a Nonlinear Programming Problem; 3.8.2 An Interior Point Algorithm; 3.8.3 A Satisfiability Heuristic 3.9 Tautology Checking in Logic Circuits |
| Record Nr. | UNINA-9910831092003321 |
Chandru Vijay <1953->
|
||
| New York, New York : , : John Wiley & Sons, Inc., , 1999 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Ottimizzazione del time offset nelle trasmissioni digitali. Tesi di laurea / laureanda Mariangela Marsano; relat. Paolo Nobili
| Ottimizzazione del time offset nelle trasmissioni digitali. Tesi di laurea / laureanda Mariangela Marsano; relat. Paolo Nobili |
| Autore | Marsano, Mariangela |
| Pubbl/distr/stampa | Lecce : Università degli Studi di Lecce. Facoltà di Scienze MM. FF. NN. Corso di laurea in Matematica, a.a. 2004-05 |
| Descrizione fisica | 72 p. ; 29 cm |
| Altri autori (Persone) | Nobili, Paolo |
| Soggetto topico | Combinatorial optimization |
| Classificazione | AMS 90C27 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | ita |
| Record Nr. | UNISALENTO-991003110689707536 |
|
Marsano, Mariangela
|
||
| Lecce : Università degli Studi di Lecce. Facoltà di Scienze MM. FF. NN. Corso di laurea in Matematica, a.a. 2004-05 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. del Salento | ||
| ||
Ottimizzazione delle operazioni di carica dei veicoli elettrici. Tesi di laurea / laureando Filandro Savino ; relatore Paolo Nobili
| Ottimizzazione delle operazioni di carica dei veicoli elettrici. Tesi di laurea / laureando Filandro Savino ; relatore Paolo Nobili |
| Autore | Savino, Filandro |
| Pubbl/distr/stampa | Lecce : Università del Salento. Facoltà di Scienze MM. FF. NN. Corso di Laurea Magistrale in Matematica, a.a. 2012-13 |
| Descrizione fisica | 80 p. ; 30 cm |
| Altri autori (Persone) | Nobili, Paolo |
| Soggetto topico |
Convex programming
Combinatorial optimization |
| Classificazione |
AMS 90C25
AMS 90C27 AMS 90C90 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | ita |
| Record Nr. | UNISALENTO-991002386749707536 |
|
Savino, Filandro
|
||
| Lecce : Università del Salento. Facoltà di Scienze MM. FF. NN. Corso di Laurea Magistrale in Matematica, a.a. 2012-13 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. del Salento | ||
| ||
Paradigms of combinatorial optimization : problems and new approaches / / edited by Vangelis Th. Paschos
| Paradigms of combinatorial optimization : problems and new approaches / / edited by Vangelis Th. Paschos |
| Edizione | [Revised and updated second edition.] |
| Pubbl/distr/stampa | London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014 |
| Descrizione fisica | 1 online resource (815 p.) |
| Disciplina | 519.64 |
| Collana | Mathematics and Statistics Series |
| Soggetto topico |
Combinatorial optimization
Programming (Mathematics) |
| ISBN |
1-119-01519-7
1-119-00535-3 1-119-01516-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
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 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; 3.5.3.2. Semi-definite relaxations; 3.5.3.3. Convex quadratic relaxations; 3.6. Conclusion; 3.7. Bibliography; Chapter 4: Mini Max 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 Mini Max 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 |
| Record Nr. | UNINA-9910132156103321 |
| London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Paradigms of combinatorial optimization : problems and new approaches / / edited by Vangelis Th. Paschos
| Paradigms of combinatorial optimization : problems and new approaches / / edited by Vangelis Th. Paschos |
| Edizione | [Revised and updated second edition.] |
| Pubbl/distr/stampa | London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014 |
| Descrizione fisica | 1 online resource (815 p.) |
| Disciplina | 519.64 |
| Collana | Mathematics and Statistics Series |
| Soggetto topico |
Combinatorial optimization
Programming (Mathematics) |
| ISBN |
1-119-01519-7
1-119-00535-3 1-119-01516-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
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 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; 3.5.3.2. Semi-definite relaxations; 3.5.3.3. Convex quadratic relaxations; 3.6. Conclusion; 3.7. Bibliography; Chapter 4: Mini Max 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 Mini Max 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 |
| Record Nr. | UNINA-9910808645503321 |
| London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Parallel combinatorial optimization [[electronic resource] /] / edited by El-Ghazali Talbi
| Parallel combinatorial optimization [[electronic resource] /] / edited by El-Ghazali Talbi |
| Pubbl/distr/stampa | Hoboken, N.J., : Wiley-Interscience, c2006 |
| Descrizione fisica | 1 online resource (348 p.) |
| Disciplina |
004.35
004/.35 |
| Altri autori (Persone) | TalbiEl-Ghazali <1965-> |
| Collana | Wiley series on parallel and distributed computing |
| Soggetto topico |
Parallel processing (Electronic computers)
Electronic data processing - Distributed processing Combinatorial optimization |
| ISBN |
1-280-72140-5
9786610721405 0-470-05392-5 0-470-05391-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
PARALLEL COMBINATORIAL OPTIMIZATION; CONTENTS; Preface; Acknowledgments; Contributors; 1. Parallel Branch-and-Bound Algorithms; 2. Parallel Dynamic Programming; 3. Parallel Branch and Cut; 4. Parallel Semidefinite Programming and Combinatorial Optimization; 5. Parallel Resolution of the Satisfiability Problem: A Survey; 6. Parallel Metaheuristics: Algorithms and Frameworks; 7. Towards Parallel Design of Hybrids between Metaheuristics and Exact Methods; 8. Parallel Exact Methods for Multiobjective Combinatorial Optimization
9. Parallel Primal-Dual Interior Point Methods for Semidefinite Programs10. MW: A Software Framework for Combinatorial Optimization on Computational Grids; 11. Constraint Logic Programming on Multiple Processors; 12. Application of Parallel Metaheuristics to Optimization Problems in Telecommunications and Bioinformatics; Index |
| Record Nr. | UNINA-9910143581203321 |
| Hoboken, N.J., : Wiley-Interscience, c2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Parallel combinatorial optimization / edited by El-Ghazali Talbi
| Parallel combinatorial optimization / edited by El-Ghazali Talbi |
| Pubbl/distr/stampa | Hoboken, N.J. : Wiley-Interscience, c2006 |
| Descrizione fisica | xvi, 330 p. : ill. ; 25 cm |
| Disciplina | 004.35 |
| Altri autori (Persone) | Talbi, El-Ghazali, 1965- |
| Collana | Wiley series on parallel and distributed computing |
| Soggetto topico |
Parallel processing (Electronic computers)
Electronic data processing - Distributed processing Combinatorial optimization |
| ISBN | 0471721018 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Record Nr. | UNISALENTO-991003783179707536 |
| Hoboken, N.J. : Wiley-Interscience, c2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. del Salento | ||
| ||
Parallel combinatorial optimization [[electronic resource] /] / edited by El-Ghazali Talbi
| Parallel combinatorial optimization [[electronic resource] /] / edited by El-Ghazali Talbi |
| Pubbl/distr/stampa | Hoboken, N.J., : Wiley-Interscience, c2006 |
| Descrizione fisica | 1 online resource (348 p.) |
| Disciplina |
004.35
004/.35 |
| Altri autori (Persone) | TalbiEl-Ghazali <1965-> |
| Collana | Wiley series on parallel and distributed computing |
| Soggetto topico |
Parallel processing (Electronic computers)
Electronic data processing - Distributed processing Combinatorial optimization |
| ISBN |
1-280-72140-5
9786610721405 0-470-05392-5 0-470-05391-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
PARALLEL COMBINATORIAL OPTIMIZATION; CONTENTS; Preface; Acknowledgments; Contributors; 1. Parallel Branch-and-Bound Algorithms; 2. Parallel Dynamic Programming; 3. Parallel Branch and Cut; 4. Parallel Semidefinite Programming and Combinatorial Optimization; 5. Parallel Resolution of the Satisfiability Problem: A Survey; 6. Parallel Metaheuristics: Algorithms and Frameworks; 7. Towards Parallel Design of Hybrids between Metaheuristics and Exact Methods; 8. Parallel Exact Methods for Multiobjective Combinatorial Optimization
9. Parallel Primal-Dual Interior Point Methods for Semidefinite Programs10. MW: A Software Framework for Combinatorial Optimization on Computational Grids; 11. Constraint Logic Programming on Multiple Processors; 12. Application of Parallel Metaheuristics to Optimization Problems in Telecommunications and Bioinformatics; Index |
| Record Nr. | UNINA-9910830916803321 |
| Hoboken, N.J., : Wiley-Interscience, c2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Parallel combinatorial optimization [[electronic resource] /] / edited by El-Ghazali Talbi
| Parallel combinatorial optimization [[electronic resource] /] / edited by El-Ghazali Talbi |
| Pubbl/distr/stampa | Hoboken, N.J., : Wiley-Interscience, c2006 |
| Descrizione fisica | 1 online resource (348 p.) |
| Disciplina |
004.35
004/.35 |
| Altri autori (Persone) | TalbiEl-Ghazali <1965-> |
| Collana | Wiley series on parallel and distributed computing |
| Soggetto topico |
Parallel processing (Electronic computers)
Electronic data processing - Distributed processing Combinatorial optimization |
| ISBN |
1-280-72140-5
9786610721405 0-470-05392-5 0-470-05391-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
PARALLEL COMBINATORIAL OPTIMIZATION; CONTENTS; Preface; Acknowledgments; Contributors; 1. Parallel Branch-and-Bound Algorithms; 2. Parallel Dynamic Programming; 3. Parallel Branch and Cut; 4. Parallel Semidefinite Programming and Combinatorial Optimization; 5. Parallel Resolution of the Satisfiability Problem: A Survey; 6. Parallel Metaheuristics: Algorithms and Frameworks; 7. Towards Parallel Design of Hybrids between Metaheuristics and Exact Methods; 8. Parallel Exact Methods for Multiobjective Combinatorial Optimization
9. Parallel Primal-Dual Interior Point Methods for Semidefinite Programs10. MW: A Software Framework for Combinatorial Optimization on Computational Grids; 11. Constraint Logic Programming on Multiple Processors; 12. Application of Parallel Metaheuristics to Optimization Problems in Telecommunications and Bioinformatics; Index |
| Record Nr. | UNINA-9910841258403321 |
| Hoboken, N.J., : Wiley-Interscience, c2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Phase transitions in combinatorial optimization problems [[electronic resource] ] : basics, algorithms and statistical mechanics / / Alexander K. Hartmann and Martin Weigt
| Phase transitions in combinatorial optimization problems [[electronic resource] ] : basics, algorithms and statistical mechanics / / Alexander K. Hartmann and Martin Weigt |
| Autore | Hartmann Alexander K |
| Pubbl/distr/stampa | Weinheim, : Wiley-VCH, c2005 |
| Descrizione fisica | 1 online resource (362 p.) |
| Disciplina | 530.13 |
| Altri autori (Persone) | WeigtMartin |
| Soggetto topico |
Statistical physics
Combinatorial optimization |
| Soggetto genere / forma | Electronic books. |
| ISBN |
1-280-85400-6
9786610854004 3-527-60673-4 3-527-60686-6 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Phase Transitions in Combinatorial Optimization Problems Basics, Algorithms and Statistical Mechanics; Contents; Preface; 1 Introduction; 1.1 Two examples of combinatorial optimization; 1.2 Why study combinatorial optimization using statistical physics?; 1.3 Textbooks; Bibliography; 2 Algorithms; 2.1 Pidgin Algol; 2.2 Iteration and recursion; 2.3 Divide-and-conquer; 2.4 Dynamic programming; 2.5 Backtracking; Bibliography; 3 Introduction to graphs; 3.1 Basic concepts and graph problems; 3.1.1 The bridges of Königsberg and Eulerian graphs; 3.1.2 Hamiltonian graphs; 3.1.3 Minimum spanning trees
3.1.4 Edge covers and vertex covers3.1.5 The graph coloring problem; 3.1.6 Matchings; 3.2 Basic graph algorithms; 3.2.1 Depth-first and breadth-first search; 3.2.2 Strongly connected component; 3.2.3 Minimum spanning tree; 3.3 Random graphs; 3.3.1 Two ensembles; 3.3.2 Evolution of graphs; 3.3.3 Finite-connectivity graphs: The case p = c/N; 3.3.4 The phase transition: Emergence of a giant component; 3.3.5 The emergence of a giant q-core; Bibliography; 4 Introduction to complexity theory; 4.1 Turing machines; 4.2 Church's thesis; 4.3 Languages; 4.4 The halting problem; 4.5 Class P; 4.6 Class NP 4.7 Definition of NP-completeness4.8 NP-complete problems; 4.8.1 Proving NP-completeness; 4.8.2 3-SAT; 4.8.3 Vertex cover; 4.9 Worst-case vs. typical-case complexity; Bibliography; 5 Statistical mechanics of the Ising model; 5.1 Phase transitions; 5.2 Some general notes on statistical mechanics; 5.2.1 The probability distribution for microscopic configurations; 5.2.2 Statistical meaning of the partition function; 5.2.3 Thermodynamic limit; 5.3 The Curie-Weiss model of a ferromagnet; 5.4 The Ising model on a random graph; 5.4.1 The model; 5.4.2 Some expectations; 5.4.3 The replica approach 5.4.4 The Bethe-Peierls approachBibliography; 6 Algorithms and numerical results for vertex covers; 6.1 Definitions; 6.2 Heuristic algorithms; 6.3 Branch-and-bound algorithm; 6.4 Results: Covering random graphs; 6.5 The leaf-removal algorithm; 6.6 Monte Carlo simulations; 6.6.1 The hard-core lattice gas; 6.6.2 Markov chains; 6.6.3 Monte Carlo for hard-core gases; 6.6.4 Parallel tempering; 6.7 Backbone; 6.8 Clustering of minimum vertex covers; Bibliography; 7 Statistical mechanics of vertex covers on a random graph; 7.1 Introduction; 7.2 The first-moment bound; 7.3 The hard-core lattice gas 7.4 Replica approach7.4.1 The replicated partition function; 7.4.2 Replica-symmetric solution; 7.4.3 Beyond replica symmetry; Bibliography; 8 The dynamics of vertex-cover algorithms; 8.1 The typical-case solution time of a complete algorithm; 8.1.1 The algorithm; 8.1.2 Some numerical observations; 8.1.3 The first descent into the tree; 8.1.4 The backtracking time; 8.1.5 The dynamical phase diagram of branch-and-bound algorithms; 8.2 The dynamics of generalized leaf-removal algorithms; 8.2.1 The algorithm; 8.2.2 Rate equations for the degree distribution; 8.2.3 Gazmuri's algorithm 8.2.4 Generalized leaf removal |
| Record Nr. | UNINA-9910144707903321 |
|
Hartmann Alexander K
|
||
| Weinheim, : Wiley-VCH, c2005 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
