LEADER 05800nam 2200745 450 001 9910132156003321 005 20200520144314.0 010 $a1-119-01507-3 010 $a1-119-00521-3 010 $a1-119-01518-9 035 $a(CKB)3710000000218297 035 $a(EBL)1765108 035 $a(SSID)ssj0001407707 035 $a(PQKBManifestationID)11818571 035 $a(PQKBTitleCode)TC0001407707 035 $a(PQKBWorkID)11410704 035 $a(PQKB)11021057 035 $a(OCoLC)891396803 035 $a(MiAaPQ)EBC1765108 035 $a(MiAaPQ)EBC4040534 035 $a(Au-PeEL)EBL1765108 035 $a(CaPaEBR)ebr10907566 035 $a(OCoLC)887507297 035 $a(Au-PeEL)EBL4040534 035 $a(CaPaEBR)ebr11113704 035 $a(CaONFJC)MIL637340 035 $a(OCoLC)927509274 035 $a(PPN)192309137 035 $a(EXLCZ)993710000000218297 100 $a20140822h20142014 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 00$aConcepts of combinatorial optimization /$fedited by Vangelis Th. Paschos 205 $aRevised and updated second edition. 210 1$aLondon, [England] ;$aHoboken, New Jersey :$cISTE :$cWiley,$d2014. 210 4$dİ2014 215 $a1 online resource (409 p.) 225 1 $aMathematics and Statistics Series (ISTE) 300 $aDescription based upon print version of record. 311 $a1-84821-656-4 320 $aIncludes bibliographical references at the end of each chapters and index. 327 $aCover; 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 327 $a2.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 327 $a3.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 327 $a3.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 327 $a4.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 327 $aChapter 5: Mixed Integer Linear Programming Models forCombinatorial Optimization Problems 330 $aCombinatorial 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 randomi 410 0$aMathematics and statistics series (ISTE) 606 $aCombinatorial optimization 606 $aProgramming (Mathematics) 615 0$aCombinatorial optimization. 615 0$aProgramming (Mathematics) 676 $a519.64 702 $aPaschos$b Vangelis Th 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910132156003321 996 $aConcepts of combinatorial optimization$92231497 997 $aUNINA