Combinatorial optimization and theoretical computer science [[electronic resource] ] : interfaces and perspectives : 30th anniversary of the LAMSADE / / edited by Vangelis Th. Paschos |
Pubbl/distr/stampa | London, : ISTE |
Descrizione fisica | 1 online resource (518 p.) |
Disciplina |
519.6/4
519.64 |
Altri autori (Persone) | PaschosVangelis Th |
Collana | ISTE |
Soggetto topico |
Combinatorial optimization - Computer programs
Computer science - Mathematics |
ISBN |
1-282-16499-6
9786612164996 0-470-61109-X 0-470-39367-X |
Classificazione |
SK 890
ST 130 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Combinatorial Optimization and Theoretical Computer Science; Contents; Preface; Chapter 1. The Complexity of Single Machine Scheduling Problems under Scenario-based Uncertainty; 1.1. Introduction; 1.2. Problem MinMax(1|prec|fmax, θ ); 1.2.1. Uncertainty on due dates; 1.2.2. Uncertainty on processing times and due dates; 1.3. Problem MinMax(1|| Σ wj Cj, Wj ); 1.4. Problem MinMax(1|| Σ Uj, θ ); 1.4.1. Uncertainty on due dates; 1.4.2. Uncertainty on processing times; 1.5. Bibliography; Chapter 2. Approximation of Multi-criteria Min and Max TSP(1, 2); 2.1. Introduction
2.1.1. The traveling salesman problem2.1.2. Multi-criteria optimization; 2.1.3. Organization of the chapter; 2.2. Overview; 2.3. The bicriteria TSP(1, 2); 2.3.1. Simple examples of the non-approximability; 2.3.2. A local search heuristic for the bicriteria TSP(1, 2); 2.3.3. A nearest neighbor heuristic for the bicriteria TSP(1, 2); 2.3.4. On the bicriteria Max TSP(1, 2); 2.4. k-criteria TSP(1, 2); 2.4.1. Non-approximability related to the number of generated solutions; 2.4.2. A nearest neighbor heuristic for the k-criteria TSP(1, 2); 2.5. Conclusion; 2.6. Bibliography Chapter 3. Online Models for Set-covering: The Flaw of Greediness3.1. Introduction; 3.2. Description of the main results and related work; 3.3. The price of ignorance; 3.4. Competitiveness of TAKE-ALL and TAKE-AT-RANDOM; 3.4.1. TAKE-ALL algorithm; 3.4.2. TAKE-AT-RANDOM algorithm; 3.5. The nasty flaw of greediness; 3.6. The power of look-ahead; 3.7. The maximum budget saving problem; 3.8. Discussion; 3.9. Bibliography; Chapter 4. Comparison of Expressiveness for Timed Automata and Time Petri Nets; 4.1. Introduction; 4.2. Time Petri nets and timed automata 4.2.1. Timed transition systems and equivalence relations4.2.2. Time Petri nets; 4.2.3. Timed automata; 4.2.4. Expressiveness and equivalence problems; 4.3. Comparison of semantics I, A and PA; 4.3.1. A first comparison between the different semantics of TPNs; 4.3.2. A second comparison for standard bounded TPN; 4.4. Strict ordering results; 4.5. Equivalence with respect to timed language acceptance; 4.5.1. Encoding atomic constraints; 4.5.2. Resetting clocks; 4.5.3. The complete construction; 4.5.4. Δ (A) and A accept the same timed language; 4.5.5. Consequences of the previous results 4.6. Bisimulation of TA by TPNs4.6.1. Regions of a timed automaton; 4.6.2. From bisimulation to uniform bisimulation; 4.6.3. A characterization of bisimilarity; 4.6.4. Proof of necessity; 4.6.5. First construction; 4.6.6. Second construction; 4.6.7. Complexity results; 4.7. Conclusion; 4.8. Bibliography; Chapter 5. A "Maximum Node Clustering" Problem; 5.1. Introduction; 5.2. Approximation algorithm for the general problem; 5.3. The tree case; 5.3.1. Dynamic programming; 5.3.2. A fully polynomial time approximation scheme; 5.4. Exponential algorithms for special cases; 5.5. Bibliography Chapter 6. The Patrolling Problem: Theoretical and Experimental Results |
Record Nr. | UNINA-9910840575603321 |
London, : ISTE | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Combinatorial Optimization Problems in Planning and Decision Making : Theory and Applications / / by Michael Z. Zgurovsky, Alexander A. Pavlov |
Autore | Zgurovsky Michael Z |
Edizione | [1st ed. 2019.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019 |
Descrizione fisica | 1 online resource (527 pages) |
Disciplina | 519.64 |
Collana | Studies in Systems, Decision and Control |
Soggetto topico |
Applied mathematics
Engineering mathematics Computer-aided engineering Industrial engineering Production engineering Operations research Decision making Mathematical and Computational Engineering Computer-Aided Engineering (CAD, CAE) and Design Industrial and Production Engineering Operations Research/Decision Theory |
ISBN | 3-319-98977-4 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Part I Intractable combinatorial optimization problems. PSC-algorithms -- Optimal scheduling for two criteria for a single machine with arbitrary due dates -- Optimal tasks execution for two criteria with a common due date on parallel machines -- Optimal scheduling for the vector criterion for parallel machines with arbitrary due dates -- The total weighted tardiness of tasks minimization on a single machine -- The total earliness/tardiness minimization on a single machine with arbitrary due dates -- The total tardiness of tasks minimization on identical parallel machines with a common due date -- Minimization of the maximum earliness/tardiness of tasks on identical parallel machines with a common due date -- The total weighted completion time of tasks minimization with precedence relations on a single machine -- Part II: Hierarchical planning and decision making in network systems with limited resources -- The four-level model of planning and decision making -- Algorithmic support of the four-level model of planning and decision making -- Models and methods of decision making with non-formalized goals -- Project 1. Informational Decision Support System for the project management in software development -- Project 2. Universal hierarchical system of scheduling and operational planning for the small-scale type of productions. |
Record Nr. | UNINA-9910337473003321 |
Zgurovsky Michael Z | ||
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2019 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Concepts of combinatorial optimization / / 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 (409 p.) |
Disciplina | 519.64 |
Collana | Mathematics and Statistics Series (ISTE) |
Soggetto topico |
Combinatorial optimization
Programming (Mathematics) |
ISBN |
1-119-01507-3
1-119-00521-3 1-119-01518-9 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Cover; Title Page; Copyright; Contents; Preface; PART I: Complexity of CombinatorialOptimization Problems; Chapter 1: Basic Concepts in Algorithmsand Complexity Theory; 1.1. Algorithmic complexity; 1.2. Problem complexity; 1.3. The classes P, NP and NPO; 1.4. Karp and Turing reductions; 1.5. NP-completeness; 1.6. Two examples of NP-complete problems; 1.6.1. MIN VERTEX COVER; 1.6.2. MAX STABLE; 1.7. A few words on strong and weak NP-completeness; 1.8. A few other well-known complexity classes; 1.9. Bibliography; Chapter 2: Randomized Complexity; 2.1. Deterministic and probabilistic algorithms
2.1.1. Complexity of a Las Vegas algorithm2.1.2. Probabilistic complexity of a problem; 2.2. Lower bound technique; 2.2.1. Definitions and notations; 2.2.2. Minimax theorem; 2.2.3. The Loomis lemma and the Yao principle; 2.3. Elementary intersection problem; 2.3.1. Upper bound; 2.3.2. Lower bound; 2.3.3. Probabilistic complexity; 2.4. Conclusion; 2.5. Bibliography; PART II: Classical Solution Methods; Chapter 3: Branch-and-Bound Methods; 3.1. Introduction; 3.2. Branch-and-bound method principles; 3.2.1. Principle of separation; 3.2.2. Pruning principles; 3.2.2.1. Bound 3.2.2.2. Evaluation function3.2.2.3. Use of the bound and of the evaluation function for pruning; 3.2.2.4. Other pruning principles; 3.2.2.5. Pruning order; 3.2.3. Developing the tree; 3.2.3.1. Description of development strategies; 3.2.3.2. Compared properties of the depth first and best first strategies; 3.3. A detailed example: the binary knapsack problem; 3.3.1. Calculating the initial bound; 3.3.2. First principle of separation; 3.3.3. Pruning without evaluation; 3.3.4. Evaluation; 3.3.5. Complete execution of the branch-and-bound method for finding only oneoptimal solution 3.3.6. First variant: finding all the optimal solutions3.3.7. Second variant: best first search strategy; 3.3.8. Third variant: second principle of separation; 3.4. Conclusion; 3.5. Bibliography; Chapter 4: Dynamic Programming; 4.1. Introduction; 4.2. A first example: crossing the bridge; 4.3. Formalization; 4.3.1. State space, decision set, transition function; 4.3.2. Feasible policies, comparison relationships and objectives; 4.4. Some other examples; 4.4.1. Stock management; 4.4.2. Shortest path bottleneck in a graph; 4.4.3. Knapsack problem; 4.5. Solution; 4.5.1. Forward procedure 4.5.2. Backward procedure4.5.3. Principles of optimality and monotonicity; 4.6. Solution of the examples; 4.6.1. Stock management; 4.6.2. Shortest path bottleneck; 4.6.3. Knapsack; 4.7. A few extensions; 4.7.1. Partial order and multicriteria optimization; 4.7.1.1. New formulation of the problem; 4.7.1.2. Solution; 4.7.1.3. Examples; 4.7.2. Dynamic programming with variables; 4.7.2.1. Sequential decision problems under uncertainty; 4.7.2.2. Solution; 4.7.2.3. Example; 4.7.3. Generalized dynamic programming; 4.8. Conclusion; 4.9. Bibliography; PART III: Elements from MathematicalProgramming Chapter 5: Mixed Integer Linear Programming Models forCombinatorial Optimization Problems |
Record Nr. | UNINA-9910132156003321 |
London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Concepts of combinatorial optimization / / 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 (409 p.) |
Disciplina | 519.64 |
Collana | Mathematics and Statistics Series (ISTE) |
Soggetto topico |
Combinatorial optimization
Programming (Mathematics) |
ISBN |
1-119-01507-3
1-119-00521-3 1-119-01518-9 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Cover; Title Page; Copyright; Contents; Preface; PART I: Complexity of CombinatorialOptimization Problems; Chapter 1: Basic Concepts in Algorithmsand Complexity Theory; 1.1. Algorithmic complexity; 1.2. Problem complexity; 1.3. The classes P, NP and NPO; 1.4. Karp and Turing reductions; 1.5. NP-completeness; 1.6. Two examples of NP-complete problems; 1.6.1. MIN VERTEX COVER; 1.6.2. MAX STABLE; 1.7. A few words on strong and weak NP-completeness; 1.8. A few other well-known complexity classes; 1.9. Bibliography; Chapter 2: Randomized Complexity; 2.1. Deterministic and probabilistic algorithms
2.1.1. Complexity of a Las Vegas algorithm2.1.2. Probabilistic complexity of a problem; 2.2. Lower bound technique; 2.2.1. Definitions and notations; 2.2.2. Minimax theorem; 2.2.3. The Loomis lemma and the Yao principle; 2.3. Elementary intersection problem; 2.3.1. Upper bound; 2.3.2. Lower bound; 2.3.3. Probabilistic complexity; 2.4. Conclusion; 2.5. Bibliography; PART II: Classical Solution Methods; Chapter 3: Branch-and-Bound Methods; 3.1. Introduction; 3.2. Branch-and-bound method principles; 3.2.1. Principle of separation; 3.2.2. Pruning principles; 3.2.2.1. Bound 3.2.2.2. Evaluation function3.2.2.3. Use of the bound and of the evaluation function for pruning; 3.2.2.4. Other pruning principles; 3.2.2.5. Pruning order; 3.2.3. Developing the tree; 3.2.3.1. Description of development strategies; 3.2.3.2. Compared properties of the depth first and best first strategies; 3.3. A detailed example: the binary knapsack problem; 3.3.1. Calculating the initial bound; 3.3.2. First principle of separation; 3.3.3. Pruning without evaluation; 3.3.4. Evaluation; 3.3.5. Complete execution of the branch-and-bound method for finding only oneoptimal solution 3.3.6. First variant: finding all the optimal solutions3.3.7. Second variant: best first search strategy; 3.3.8. Third variant: second principle of separation; 3.4. Conclusion; 3.5. Bibliography; Chapter 4: Dynamic Programming; 4.1. Introduction; 4.2. A first example: crossing the bridge; 4.3. Formalization; 4.3.1. State space, decision set, transition function; 4.3.2. Feasible policies, comparison relationships and objectives; 4.4. Some other examples; 4.4.1. Stock management; 4.4.2. Shortest path bottleneck in a graph; 4.4.3. Knapsack problem; 4.5. Solution; 4.5.1. Forward procedure 4.5.2. Backward procedure4.5.3. Principles of optimality and monotonicity; 4.6. Solution of the examples; 4.6.1. Stock management; 4.6.2. Shortest path bottleneck; 4.6.3. Knapsack; 4.7. A few extensions; 4.7.1. Partial order and multicriteria optimization; 4.7.1.1. New formulation of the problem; 4.7.1.2. Solution; 4.7.1.3. Examples; 4.7.2. Dynamic programming with variables; 4.7.2.1. Sequential decision problems under uncertainty; 4.7.2.2. Solution; 4.7.2.3. Example; 4.7.3. Generalized dynamic programming; 4.8. Conclusion; 4.9. Bibliography; PART III: Elements from MathematicalProgramming Chapter 5: Mixed Integer Linear Programming Models forCombinatorial Optimization Problems |
Record Nr. | UNINA-9910821363403321 |
London, [England] ; ; Hoboken, New Jersey : , : ISTE : , : Wiley, , 2014 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Concepts of combinatorial optimization [[electronic resource] /] / edited by Vangelis Th. Paschos |
Pubbl/distr/stampa | London, : ISTE |
Descrizione fisica | 1 online resource (382 p.) |
Disciplina | 519.64 |
Altri autori (Persone) | PaschosVangelis Th |
Collana |
ISTE
Combinatorial optimization |
Soggetto topico |
Combinatorial optimization
Programming (Mathematics) |
Soggetto genere / forma | Electronic books. |
ISBN |
1-118-60024-X
1-118-60023-1 1-299-18744-7 1-118-60019-3 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | pt. I. Complexity of combinatorial optimization problems -- pt. II. Classical solution methods -- pt. III. Elements from mathematical programming. |
Record Nr. | UNINA-9910141489303321 |
London, : ISTE | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Concepts of combinatorial optimization [[electronic resource] /] / edited by Vangelis Th. Paschos |
Pubbl/distr/stampa | London, : ISTE |
Descrizione fisica | 1 online resource (382 p.) |
Disciplina | 519.64 |
Altri autori (Persone) | PaschosVangelis Th |
Collana |
ISTE
Combinatorial optimization |
Soggetto topico |
Combinatorial optimization
Programming (Mathematics) |
ISBN |
1-118-60024-X
1-118-60023-1 1-299-18744-7 1-118-60019-3 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | pt. I. Complexity of combinatorial optimization problems -- pt. II. Classical solution methods -- pt. III. Elements from mathematical programming. |
Record Nr. | UNINA-9910830017403321 |
London, : ISTE | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Concepts of combinatorial optimization [[electronic resource] /] / edited by Vangelis Th. Paschos |
Pubbl/distr/stampa | London, : ISTE |
Descrizione fisica | 1 online resource (382 p.) |
Disciplina | 519.64 |
Altri autori (Persone) | PaschosVangelis Th |
Collana |
ISTE
Combinatorial optimization |
Soggetto topico |
Combinatorial optimization
Programming (Mathematics) |
ISBN |
1-118-60024-X
1-118-60023-1 1-299-18744-7 1-118-60019-3 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | pt. I. Complexity of combinatorial optimization problems -- pt. II. Classical solution methods -- pt. III. Elements from mathematical programming. |
Record Nr. | UNINA-9910841642603321 |
London, : ISTE | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Discrete Cuckoo Search for Combinatorial Optimization [[electronic resource] /] / by Aziz Ouaarab |
Autore | Ouaarab Aziz |
Edizione | [1st ed. 2020.] |
Pubbl/distr/stampa | Singapore : , : Springer Singapore : , : Imprint : Springer, , 2020 |
Descrizione fisica | 1 online resource (138 pages) |
Disciplina | 519.64 |
Collana | Springer Tracts in Nature-Inspired Computing |
Soggetto topico |
Computational intelligence
Mathematical optimization Algorithms Computational Intelligence Discrete Optimization Algorithm Analysis and Problem Complexity |
ISBN | 981-15-3836-0 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Combinatorial optimization space -- Solving COPs -- From CS to DCS -- DCS and the studied COPs -- Cuckoo search Random key encoding. |
Record Nr. | UNINA-9910768434503321 |
Ouaarab Aziz | ||
Singapore : , : Springer Singapore : , : Imprint : Springer, , 2020 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Dual-Feasible Functions for Integer Programming and Combinatorial Optimization : Basics, Extensions and Applications / / by Cláudio Alves, Francois Clautiaux, José Valério de Carvalho, Jürgen Rietz |
Autore | Alves Cláudio |
Edizione | [1st ed. 2016.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2016 |
Descrizione fisica | 1 online resource (XI, 159 p. 38 illus. in color.) |
Disciplina | 519.64 |
Collana | EURO Advanced Tutorials on Operational Research |
Soggetto topico |
Operations research
Decision making Management science Mathematical optimization Operations Research/Decision Theory Operations Research, Management Science Discrete Optimization |
ISBN | 3-319-27604-2 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Linear and Integer Programming -- Classical Dual-feasible Functions -- General Dual-feasible Functions -- Applications for Cutting and Packing Problems -- Other Applications in General Integer Programming. . |
Record Nr. | UNINA-9910254959803321 |
Alves Cláudio | ||
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2016 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Dynamic programming multi-objective combinatorial optimization / / Michal Mankowski, Mikhail Moshkov |
Autore | Mankowski Michal |
Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2021] |
Descrizione fisica | 1 online resource (213 pages) : illustrations |
Disciplina | 519.64 |
Soggetto topico |
Computational intelligence
Programming techniques Programació dinàmica Optimització combinatòria |
Soggetto genere / forma | Llibres electrònics |
ISBN | 3-030-63920-7 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Record Nr. | UNINA-9910484820703321 |
Mankowski Michal | ||
Cham, Switzerland : , : Springer, , [2021] | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|