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