Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos |
Autore | Murat Cecile |
Pubbl/distr/stampa | London ; ; Newport Beach, CA, : ISTE, 2006 |
Descrizione fisica | 1 online resource (269 p.) |
Disciplina |
511.6
519.2 |
Altri autori (Persone) | PaschosVangelis Th |
Collana | ISTE |
Soggetto topico |
Combinatorial probabilities
Combinatorial optimization Random graphs |
Soggetto genere / forma | Electronic books. |
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 | eng |
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 |
Record Nr. | UNINA-9910143315903321 |
Murat Cecile | ||
London ; ; Newport Beach, CA, : ISTE, 2006 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos |
Autore | Murat Cecile |
Pubbl/distr/stampa | London ; ; Newport Beach, CA, : ISTE, 2006 |
Descrizione fisica | 1 online resource (269 p.) |
Disciplina |
511.6
519.2 |
Altri autori (Persone) | PaschosVangelis Th |
Collana | ISTE |
Soggetto topico |
Combinatorial probabilities
Combinatorial optimization Random 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 | eng |
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 |
Record Nr. | UNISA-996216942703316 |
Murat Cecile | ||
London ; ; Newport Beach, CA, : ISTE, 2006 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos |
Autore | Murat Cecile |
Pubbl/distr/stampa | London ; ; Newport Beach, CA, : ISTE, 2006 |
Descrizione fisica | 1 online resource (269 p.) |
Disciplina |
511.6
519.2 |
Altri autori (Persone) | PaschosVangelis Th |
Collana | ISTE |
Soggetto topico |
Combinatorial probabilities
Combinatorial optimization Random 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 | eng |
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 |
Record Nr. | UNINA-9910830041603321 |
Murat Cecile | ||
London ; ; Newport Beach, CA, : ISTE, 2006 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Probabilistic combinatorial optimization on graphs [[electronic resource] /] / Cécile Murat and Vangelis Th. Paschos |
Autore | Murat Cecile |
Pubbl/distr/stampa | London ; ; Newport Beach, CA, : ISTE, 2006 |
Descrizione fisica | 1 online resource (269 p.) |
Disciplina |
511.6
519.2 |
Altri autori (Persone) | PaschosVangelis Th |
Collana | ISTE |
Soggetto topico |
Combinatorial probabilities
Combinatorial optimization Random 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 | eng |
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 |
Record Nr. | UNINA-9910841663103321 |
Murat Cecile | ||
London ; ; Newport Beach, CA, : ISTE, 2006 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|