東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Concepts of combinatorial optimization

Paschos, Vangelis Th.

Linked to FindBook

Google Book

Amazon

博客來

Concepts of combinatorial optimization

Record Type:	Electronic resources : Monograph/item
Title/Author:	Concepts of combinatorial optimization/ edited by Vangelis Th. Paschos.
other author:	Paschos, Vangelis Th.
Published:	Hoboken :Wiley, : 2014.,
Description:	1 online resource (409 p.)
[NT 15003449]:	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.
[NT 15003449]:	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.
[NT 15003449]:	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.
[NT 15003449]:	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.
[NT 15003449]:	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.
Subject:	Combinatorial optimization. -
Online resource:	http://onlinelibrary.wiley.com/book/10.1002/9781119005216
ISBN:	9781119005216

Concepts of combinatorial optimization
Concepts of combinatorial optimization[electronic resource] /edited by Vangelis Th. Paschos. - 2nd ed. - Hoboken :Wiley,2014. - 1 online resource (409 p.) - ISTE. - ISTE..

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.

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 topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization. Concepts of Combinatorial Optimization, is divided into three parts:- On the complexity of combinatorial optimization problems, presenting basics abo.

ISBN: 9781119005216Subjects--Topical Terms:

544215
Combinatorial optimization.

LC Class. No.: QA402.5 / .C545123 2014

Dewey Class. No.: 519.64

Concepts of combinatorial optimization
LDR:04691cmm a2200373Mi 4500 001 2002876
003 OCoLC
005 20141125181957.0
006 m o d
007 cr |||||||||||
008 151223s2014 nju o 000 0 eng d
020 $a 9781119005216 $q electronic bk.
020 $a 1119005213 $q electronic bk.
020 $a 9781119015185 $q electronic bk.
020 $a 1119015189 $q electronic bk.
020 $z 9781848216563
020 $z 1848216564
035 $a (OCoLC)887507297
035 $a ocn887507297
040 $a EBLCP $b eng $c EBLCP $d MHW $d DG1 $d N $d OCLCQ $d VRC
050 4 $a QA402.5 $b .C545123 2014
082 0 4 $a 519.64 $2 23
245 0 0 $a Concepts of combinatorial optimization $h [electronic resource] / $c edited by Vangelis Th. Paschos.
250 $a 2nd ed.
260 $a Hoboken : $b Wiley, $c 2014.
300 $a 1 online resource (409 p.)
490 1 $a ISTE
505 0 $a 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.
505 8 $a 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.
505 8 $a 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.
505 8 $a 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.
505 8 $a 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.
520 $a 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 topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization. Concepts of Combinatorial Optimization, is divided into three parts:- On the complexity of combinatorial optimization problems, presenting basics abo.
588 $a Description based on print version record.
650 0 $a Combinatorial optimization. $3 544215
650 0 $a Programming (Mathematics) $3 547124
700 1 $a Paschos, Vangelis Th. $3 1314724
830 0 $a ISTE. $3 2084372
856 4 0 $u http://onlinelibrary.wiley.com/book/10.1002/9781119005216