本文研究一些最优化约束满足问题的计算复杂性、近似算法以及近似困难性。包括：构造了一个同时优化查询复杂度、随机源以及可靠性三个参数之间权衡的群上同态函数局部检测系统，该结果适用于更广范围最大化约束满足问题实例的近似困难性证明；研究了可满足Max3CSPq、图的标签割集(LabelCut)相关问题以及最少感染(Min Contamination)相关问题的近似算法和近似困难性，我们的结果给出这些问题目前已知最好的复杂性、近似算法或近似困难性结果。具体介绍如下：　　 在第一部分中，构造了一个关于群上同态函数的去随机化图检测系统。该系统同时优化查询复杂度、随机源以及可靠性三个参数之间的权衡，弥补了以前的同态函数局部检测系统的缺陷：要么只优化查询复杂度跟可靠性之间的权衡，要么只优化随机源跟可靠性之间的权衡。我们改进后的检测系统可以应用于代数性质局部检测系统以及概率验证系统的构造中，适用于更广范围最大化约束满足问题实例的近似困难性证明。　　 在第二部分中，研究可满足Max3CSPq的近似困难性，其中素数q≠3。给出了如下的条件近似困难结果：基于d-1 Games Conjecture[83](适当的d)，我们证明可满足Max3CSPq不存在近似比好于(1/q+1/q2-1/q3)+ε的近似算法。事实上，我们构造了一个特殊的3元q维谓词F，并证明Max CSP(F)实例即使在可满足的前提下也是Approximation Resistant的，即不存在比随机赋值算法更优的近似算法。我们的结论有助于刻画哪些谓词F对应的可满足MaxCSP(F)是Approximation Resistant的，而我们的方法可能用于证明更多可满足Max kCSPq的近似困难结果。　　 在第三部分中，研究标签割集相关问题的近似性。利用线性规划给出最小标签(s-t)割集问题近似比min｛O(√m/OPT)，O(n2/3/OPT1/3)｝的近似算法(其中m和n分别是给定实例图中边和顶点数目而OPT是给定实例的最优值)，同时我们还利用概率的方法证明所用的线性松弛即使再加上一些更合理且严格的约束仍然具有Ω(√m/OPT)的Integrality Gap。我们首次研究最大标签割集相关问题的近似性，利用半正定规划给出最大标签(s-t)割集问题近似比为0.63的近似算法，并证明对任意ε＞0，这些问题都不存在近似比好于0.75+ε的近似算法(基于P≠NP)。　　 在第四部分中，研究最小感染相关问题的计算复杂性和近似性。证明Minimum Average Contamination Problem和Minimum Worst ContaminationProblem在一些特殊图(二部图、幂律图等)上是NP-困难的。我们利用线性规划给出Minimum Average Contamination Problem近似比为(1+ε，O(logn))的双参近似算法(对任意ε＞0)，与目前己知的Minimum Worst ContaminationProblem的(1+ε，O(logn))双参近似算法匹配。同时，我们证明在单参数的意义下，我们所使用的线性松弛具有Ω(n)的Integrality Gap。在近似困难性方面，我们证明这两个问题目前已知最好的常数近似困难结果。　　 最小标签割集问题在网络安全领域特别是在多层次网络防控恶意入侵中有着重要的应用。最大标签割集相关问题在通信网络领域特别是新技术通信及网络设备互联中有着重要的应用。最小感染问题主要应用于大型复杂网络中病毒传播控制。关于这些问题的研究成果有着广泛的理论意义和应用前景。我们在证明过程中所使用的思路和技术可以应用于其他更多组合优化问题的复杂性及近似性研究中。关于这些优化问题的理论研究也为在现实世界网络大规模研究及应用这类问题提供了理论和技术资源。