网络优化问题以及网络改进问题是图论和组合最优化领域的一个重要的研究方向。这些问题在现实生活中有广泛的应用,研究其具有重要的意义。网络优化问题主要研究如何在一定的约束条件下寻求问题的最优解,而网络改进问题又称为网络优化问题的反问题,它研究如何通过修改问题模型的参数,使得在修改后的参数下,网络能满足问题的某些特定的约束或要求,并且总的修改费用最少。本文对k-supplier问题、l∞模下一类通信网络的改进问题以及圈秩数固定的最小连通生成子图的部分改进问题进行了研究,并分别得到了近似算法及多项式时间算法：　　第一,研究了k-supplierk问题,得到了性能比为3的贪婪近似算法。k-supplier问题是一个NP-困难问题,且其最优近似性能比为3。本文对k-supplier问题通过使用贪婪技术,从客户的角度出发,不断寻找最近的供应商,通过迭代调整,得到了该问题的3-近似的多项式时间贪婪近似算法,并通过实例验证了该算法的有效性。该算法相对于其他方法具有实现简单,计算速度快,结果精度较高等优点。　　第二,研究了l∞模下一类通信网络的改进问题,该问题具有一定的应用背景。本文对一类特定的通信网络优化问题,运用弱控制集的定义,首先基于最小生成树算法,得到了求解该通信网络优化问题的复杂性为O(｜V｜2)的多项式时间算法,并在此基础上得到了其改进问题的模型。通过一类Newton型算法进行求解,得到了其改进问题的复杂性为O(｜V｜2(log｜E｜+｜V｜))的多项式时间算法。　　第三,研究了圈秩数固定的最小连通生成子图的部分改进问题。对于给定子图是圈秩数为k的连通子图的情况,首先收缩该子图,得到收缩之后图的最小生成树。在此生成树的基础上进行扩展,最后得到部分改进问题的多项式时间算法;对于给定子图为生成树的情况,通过逐步减少给定子图边的权重,构造出一个包含给定子图的圈秩数为k的连通子图,并证明了该连通子图为最小连通生成子图,从而得到了该类情形下部分改进问题的多项式时间算法。