05800nam 2200745 450 991013215600332120200520144314.01-119-01507-31-119-00521-31-119-01518-9(CKB)3710000000218297(EBL)1765108(SSID)ssj0001407707(PQKBManifestationID)11818571(PQKBTitleCode)TC0001407707(PQKBWorkID)11410704(PQKB)11021057(OCoLC)891396803(MiAaPQ)EBC1765108(MiAaPQ)EBC4040534(Au-PeEL)EBL1765108(CaPaEBR)ebr10907566(OCoLC)887507297(Au-PeEL)EBL4040534(CaPaEBR)ebr11113704(CaONFJC)MIL637340(OCoLC)927509274(PPN)192309137(EXLCZ)99371000000021829720140822h20142014 uy 0engur|n|---|||||txtccrConcepts of combinatorial optimization /edited by Vangelis Th. PaschosRevised and updated second edition.London, [England] ;Hoboken, New Jersey :ISTE :Wiley,2014.©20141 online resource (409 p.)Mathematics and Statistics Series (ISTE)Description based upon print version of record.1-84821-656-4 Includes bibliographical references at the end of each chapters and index.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 algorithms2.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. Bound3.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 solution3.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 procedure4.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 MathematicalProgrammingChapter 5: Mixed Integer Linear Programming Models forCombinatorial Optimization ProblemsCombinatorial 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 about worst-case and randomiMathematics and statistics series (ISTE)Combinatorial optimizationProgramming (Mathematics)Combinatorial optimization.Programming (Mathematics)519.64Paschos Vangelis ThMiAaPQMiAaPQMiAaPQBOOK9910132156003321Concepts of combinatorial optimization2231497UNINA