主对偶方法路径长度受限顶点多路割问题本论文主要以线性规划为工具对一类图上覆盖问题的算法进行了研究。在讨论这一类图上覆盖问题共有的线性规划模型基础上，具体针对混合支配问题和路径长度受限多路割问题进行了研究。对混合支配问题给出了3倍近似算法；对路径长度受限多路割问题给出了倍近似算法。　　图上的混合支配集是图中的一个点和边组成的混合集合，使得对于图中的任意一条边或一个顶点，若其不在混合支配集中，则其必须与该集合中的某条边或某个顶点相邻（邻接）。混合支配问题要求在图中找到一个基数最小的混合支配集。带权混合支配问题则是混合支配问题的一个自然推广，其将图中的点和边赋予不同的权重进行区分。令图中的所有点的权重均为wu，所有边的权重均为we，带权混合支配问题要求找到一个混合支配集使得其点和边的权重之和达到最小。若权重满足wu≤we时，则称其为点优先带权混合支配问题。对于点优先带权混合支配问题的近似算法目前还鲜有研究，已知的一个2倍近似算法[1]无法推广到带权情况下，本文通过将混合支配问题与点覆盖问题建立联系直接得到了一个点优先带权混合支配问题的4倍近似算法。之后本文利用Nemhauser and Trotter定理中相关线性规划模型最优解的半整性性质，讨论Nemhauser and Trotter定理与皇冠分解的关系，最后使用这些结论设计了一个点优先带权混合支配问题的3倍近似算法。　　一个路径长度受限顶点多路割是图中的一个顶点集，使得从图中删去该顶点集后，图中任意两个给定的端点之间不存在长度小于等于L的路径。路径长度受限顶点多路割问题要求找到一个权重最小的顶点割集。当问题中的端点数为2时，路径长度受限顶点多路割问题就是路径长度受限最小割问题，对于该问题文献[2]给出了一个近似率为O(L)的近似算法。但是关于路径长度受限顶点多路割问题的近似算法还鲜有研究。本文基于线性规划方法，使用主对偶模式设计了一个路径长度受限顶点多路割问题的L倍近似算法，并且证明了基于本文所使用的线性规划模型，以上近似算法的近似率在忽略常数意义下是使用线性规划方法设计该问题近似算法的最优近似率。