Title Page
Abstract
Contents
Chapter 1. Introduction 11
1.1. Related Problems 14
1.2. Objectives and contributions 18
Chapter 2. Polyhedral Study 21
2.1. Introduction 21
2.1.1. Arc-Flow Formulation 23
2.1.2. Relationships with Other Formulations 25
2.1.3. Other Methods 29
2.2. Basic Properties of Arc-Flow Formulation 31
2.2.1. Necessary Conditions of Facet-defining Inequality 31
2.3. Valid Inequalities for the Arc-Flow Formulation 36
2.3.1. Facet-defining Inequalities: 3-Criteria Inequality 37
2.3.2. Other Valid Inequalities 58
2.4. Triple Formulation 67
2.4.1. Triple Formulation and Basic Properties 67
2.4.2. 3-Criteria-TF Inequality 70
2.4.3. Other Valid Inequalities for the Triple Formulation 73
Chapter 3. Approximation Algorithm 77
3.1. Introduction 77
3.2. Inapproximability Results 81
3.2.1. Integrality Gap 81
3.2.2. Inapproximability of sMTP 83
3.3. Approximation of some special classes of sMTP 86
3.3.1. An FPTAS for the single-source sMTP 87
3.3.2. An approximation algorithm for the t-separable sMTP 92
3.3.3. Boosting approximability of the t-separable sMTP's with large rratio 95
3.4. Approximation of general sMTP 104
3.4.1. Reducing sMTP to t-intersecting sMTP 104
3.4.2. Reducing t-intersecting sMTP to t-separable sMTP 105
3.5. Applying to Other Problems 108
3.5.1. Approximation algorithm for TRPP 110
3.5.2. Hardness of Approximation 114
3.6. Conclusion 117
Chapter 4. Comparative Experiments 118
4.1. Introduction 118
4.2. Experimental Setting 119
4.3. Computational Comparison of Relaxation Bounds 120
4.4. Comparison of Computation time Based on the use of Cut 123
4.5. Comparison of Heuristic Algorithms 126
Chapter 5. Conclusion 130
5.1. Summary of contributions 130
5.2. Further Research Directions 132
Bibliography 134
국문초록 144
Table 2.1. The partition of the y, x-variables, and the f-variables {fijkl : 1 ≤ k ≤ i 〈j 〈l ≤ n, ki, ij, jl∈ A₂₃} in R for extension of M and the corresponding cases.[이미지참조] 44
Table 2.2. The partition of the remaining f-variables {fijkl : 1 ≤ k ≤ i 〈j 〈l ≤n, ki, ij, or jl ∈ A₂₃} in R for incremental extension of M and the corresponding cases.[이미지참조] 45
Table 2.3. Affinely independent vectors with 0=0 65
Table 4.1. Test result with rctype=C 124
Table 4.2. Test result with n=35, rctype=B 125
Table 4.3. Comparison on the gap between method outputs and optimal solutions 129
Figure 2.1. Apq's, Cpq's, π.[이미지참조] 37
Figure 2.2. Solutions in the necessity proof 40
Figure 2.3. Lower triagularization technique 42
Figure 2.4. The three subcases of Case 1-2 47
Figure 3.1. An n=9 instance with large gap 82
Figure 4.1. LP gap comparison for different formulations 122
Figure 4.2. Computation time comparison for different formulations 123