LEADER 05619nam 22007574a 450 001 9910143315903321 005 20210209180957.0 010 $a1-280-51061-7 010 $a9786610510610 010 $a1-84704-483-2 010 $a0-470-39464-1 010 $a0-470-61250-9 010 $a1-84704-583-9 035 $a(CKB)1000000000335550 035 $a(EBL)700743 035 $a(OCoLC)769341529 035 $a(SSID)ssj0000227838 035 $a(PQKBManifestationID)11225780 035 $a(PQKBTitleCode)TC0000227838 035 $a(PQKBWorkID)10269942 035 $a(PQKB)11186106 035 $a(MiAaPQ)EBC700743 035 $a(MiAaPQ)EBC261393 035 $a(MiAaPQ)EBC4036821 035 $a(Au-PeEL)EBL261393 035 $a(OCoLC)501313838 035 $a(EXLCZ)991000000000335550 100 $a20060110d2006 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aProbabilistic combinatorial optimization on graphs$b[electronic resource] /$fCe?cile Murat and Vangelis Th. Paschos 210 $aLondon ;$aNewport Beach, CA $cISTE$d2006 215 $a1 online resource (269 p.) 225 1 $aISTE ;$vv.105 300 $aDescription based upon print version of record. 311 $a1-905209-33-9 320 $aIncludes bibliographical references (p. [255]-259) and index. 327 $aProbabilistic Combinatorial Optimization on Graphs; Contents; Preface; Chapter 1. A Short Insight into Probabilistic Combinatorial Optimization; 1.1. Motivations and applications; 1.2. A formalism for probabilistic combinatorial optimization; 1.3. The main methodological issues dealing with probabilistic combinatorial optimization; 1.3.1. Complexity issues; 1.3.1.1. Membership in NPO is not always obvious; 1.3.1.2. Complexity of deterministic vs. complexity of probabilistic optimization problems; 1.3.2. Solution issues; 1.3.2.1. Characterization of optimal a priori solutions 327 $a1.3.2.2. Polynomial subcases1.3.2.3. Exact solutions and polynomial approximation issues; 1.4. Miscellaneous and bibliographic notes; First Part. Probabilistic Graph-Problems; Chapter 2. The Probabilistic Maximum Independent Set; 2.1. The modification strategies and a preliminary result; 2.1.1. Strategy M1; 2.1.2. Strategies M2 and M3; 2.1.3. Strategy M4; 2.1.4. Strategy M5; 2.1.5. A general mathematical formulation for the five functionals; 2.2. PROBABILISTIC MAX INDEPENDENT SET1; 2.2.1. Computing optimal a priori solutions; 2.2.2. Approximating optimal solutions 327 $a2.2.3. Dealing with bipartite graphs2.3. PROBABILISTIC MAX INDEPENDENT SET2 and 3; 2.3.1. Expressions for E(G, S, M2) and E(G, S, M3); 2.3.2. An upper bound for the complexity of E(G, S, M2); 2.3.3. Bounds for E(G, S, M2); 2.3.4. Approximating optimal solutions; 2.3.4.1. Using argmax {?viESpi} as an a priori solution; 2.3.4.2. Using approximations of MAX INDEPENDENT SET; 2.3.5. Dealing with bipartite graphs; 2.4. PROBABILISTIC MAX INDEPENDENT SET4; 2.4.1. An expression for E(G, S, M4); 2.4.2. Using S* or argmax{?viESpi} as an a priori solution; 2.4.3. Dealing with bipartite graphs 327 $a2.5. PROBABILISTIC MAX INDEPENDENT SET52.5.1. In general graphs; 2.5.2. In bipartite graphs; 2.6. Summary of the results; 2.7. Methodological questions; 2.7.1. Maximizing a criterion associated with gain; 2.7.1.1. The minimum gain criterion; 2.7.1.2. The maximum gain criterion; 2.7.2. Minimizing a criterion associated with regret; 2.7.2.1. The maximum regret criterion; 2.7.3. Optimizing expectation; 2.8. Proofs of the results; 2.8.1. Proof of Proposition 2.1; 2.8.2. Proof of Theorem 2.6; 2.8.3. Proof of Proposition 2.3; 2.8.4. Proof of Theorem 2.13 327 $aChapter 3. The Probabilistic Minimum Vertex Cover3.1. The strategies M1, M2 and M3 and a general preliminary result; 3.1.1. Specification of M1, M2 and M3; 3.1.1.1. Strategy M1; 3.1.1.2. Strategy M2; 3.1.1.3. Strategy M3; 3.1.2. A first expression for the functionals; 3.2. PROBABILISTIC MIN VERTEX COVER1; 3.3. PROBABILISTIC MIN VERTEX COVER2; 3.4. PROBABILISTIC MIN VERTEX COVER3; 3.4.1. Building E(G, C, M3); 3.4.2. Bounds for E(G, C, M3); 3.5. Some methodological questions; 3.6. Proofs of the results; 3.6.1. Proof of Theorem 3.3; 3.6.2. On the the bounds obtained in Theorem 3.3 327 $aChapter 4. The Probabilistic Longest Path 330 $aThis title provides a comprehensive survey over the subject of probabilistic combinatorial optimization, discussing probabilistic versions of some of the most paradigmatic combinatorial problems on graphs, such as the maximum independent set, the minimum vertex covering, the longest path and the minimum coloring. Those who possess a sound knowledge of the subject mater will find the title of great interest, but those who have only some mathematical familiarity and knowledge about complexity and approximation theory will also find it an accessible and informative read. 410 0$aISTE 606 $aCombinatorial probabilities 606 $aCombinatorial optimization 606 $aRandom graphs 608 $aElectronic books. 615 0$aCombinatorial probabilities. 615 0$aCombinatorial optimization. 615 0$aRandom graphs. 676 $a511.6 676 $a519.2 700 $aMurat$b Cecile$0978945 701 $aPaschos$b Vangelis Th$0944252 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910143315903321 996 $aProbabilistic combinatorial optimization on graphs$92231453 997 $aUNINA LEADER 02077nam 2200613 a 450 001 9910778771103321 005 20230421033152.0 010 $a0-309-17451-1 010 $a1-280-21057-5 010 $a9786610210572 010 $a0-309-55342-3 010 $a0-585-03709-4 035 $a(CKB)110986584752092 035 $a(OCoLC)42636413 035 $a(CaPaEBR)ebrary10062904 035 $a(SSID)ssj0000108150 035 $a(PQKBManifestationID)11745615 035 $a(PQKBTitleCode)TC0000108150 035 $a(PQKBWorkID)10044660 035 $a(PQKB)11018275 035 $a(MiAaPQ)EBC3376990 035 $a(Au-PeEL)EBL3376990 035 $a(CaPaEBR)ebr10062904 035 $a(OCoLC)923267553 035 $a(EXLCZ)99110986584752092 100 $a19971006d1997 uy 0 101 0 $aeng 135 $aurcn||||||||| 181 $ctxt 182 $cc 183 $acr 200 00$aAviation fuels with improved fire safety$b[electronic resource] $ea proceedings /$fCommittee on Aviation Fuels with Improved Fire Safety, National Research Council 210 $aWashington, D.C. $cNational Academy Press$d1997 215 $a1 online resource (157 p.) 300 $a"NMAB-490." 300 $aPapers from the Workshop on Aviation Fuels with Improved Fire Safety, held on November 19-20, 1996 at the Nation Research Council's Georgetown Facility, Washington, D.C. 311 $a0-309-05833-3 320 $aIncludes bibliographical references. 606 $aAirplanes$xFuel 606 $aAirplanes$xFuel consumption 606 $aFire prevention 615 0$aAirplanes$xFuel. 615 0$aAirplanes$xFuel consumption. 615 0$aFire prevention. 676 $a629.134/351 712 02$aNational Research Council (U.S.) 712 02$aNational Research Council (U.S.).$bCommittee on Aviation Fuels with Improved Fire Safety. 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910778771103321 996 $aAviation fuels with improved fire safety$93772442 997 $aUNINA