Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos

• Autore: Murat Cecile
• Pubblicazione: London ; ; Newport Beach, CA, : ISTE, 2006
• Descrizione fisica: 1 online resource (269 p.)
• Disciplina: 511.6; 519.2
• Soggetto topico: Combinatorial probabilities; Combinatorial optimization; Random graphs
• Altri autori: PaschosVangelis Th
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references (p. [255]-259) and index.
• Nota di contenuto: Probabilistic 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 ; 1.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 ; 2.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 ; 2.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 ; Chapter 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 ; Chapter 4. The Probabilistic Longest Path
• Sommario/riassunto: This 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.
• Titolo autorizzato: Probabilistic combinatorial optimization on graphs
• ISBN: 1-280-51061-7; 9786610510610; 1-84704-483-2; 0-470-39464-1; 0-470-61250-9; 1-84704-583-9
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910841663103321
• Lo trovi qui: Univ. Federico II
• Serie: ISTE