國立虎尾科技大學 |

Concepts of combinatorial optimization

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Concepts of combinatorial optimization/ edited by Vangelis Th. Paschos.
其他作者:	Paschos, Vangelis Th.
出版者:	Hoboken :Wiley, : 2014.,
面頁冊數:	1 online resource (409 p.)
標題:	Combinatorial optimization. -
電子資源:	http://onlinelibrary.wiley.com/book/10.1002/9781119005216
ISBN:	9781119005216$qelectronic bk.

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: 9781119005216$qelectronic bk.Subjects--Topical Terms:

528128
Combinatorial optimization.

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

Dewey Class. No.: 519.64

Concepts of combinatorial optimization
LDR:04691cam a2200373Mi 4500 001 831239
003 OCoLC
005 20141125181957.0
006 m o d
007 cr |||||||||||
008 160215s2014 nju o 000 0 eng d
020 $a 9781119005216$qelectronic bk.
020 $a 1119005213$qelectronic bk.
020 $a 9781119015185$qelectronic bk.
020 $a 1119015189$qelectronic 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 528128
650 0 $a Programming (Mathematics) $3 528016
700 1 $a Paschos, Vangelis Th. $3 1059017
830 0 $a ISTE. $3 999840
856 4 0 $u http://onlinelibrary.wiley.com/book/10.1002/9781119005216