| Abstract (in English) | 第3页 |
| Abstract (in Chinese) | 第4-6页 |
| Chapter 1 Introduction | 第6-18页 |
| 1.1 The background of cover problem and steiner tree problem | 第6-13页 |
| 1.2 Basic knowledge | 第13-14页 |
| 1.3 Related work of cover problem and steiner tree problem | 第14-16页 |
| 1.4 Our results of cover problem and steiner tree problem | 第16-17页 |
| 1.5 Organization of the thesis | 第17-18页 |
| Chapter 2 Primal-Dual Algorithm | 第18-23页 |
| 2.1 Induction and history | 第18-19页 |
| 2.2 The classic primal-dual method | 第19-23页 |
| Chapter 3 Stochastic Set Cover Problem with Submodular Penalties | 第23-37页 |
| 3.1 Introduction of the problem | 第23-26页 |
| 3.2 The primal-dual algorithm | 第26-29页 |
| 3.3 The analysis of the algorithm | 第29-37页 |
| Chapter 4 Stochastic Prize-Collecting Steiner Tree Problem | 第37-47页 |
| 4.1 Introduction of the problem | 第37-40页 |
| 4.2 The primal-dual algorithm | 第40-42页 |
| 4.3 The analysis of the algorithm | 第42-47页 |
| Chapter 5 Conclusion | 第47-48页 |
| Bibliography | 第48-53页 |
| Acknowledgements | 第53页 |
