网络连通控制集和斯坦纳树变形的近似算法

本项目主要研究网络上NP-完备最优化问题的近似算法，重点考察单位圆盘图上的连通控制集问题和斯坦纳树问题的变形。对于单位圆盘图上的连通控制集问题，本项目在已取得的研究成果的基础上，深入研究连通控制集和极大独立集之间的关系，并考察由MCDS生成区域的洞与MCDS大小之间的关系，希望改进现有算法的近似比，进而探索新的近似算法；本项目通过比较经典斯坦纳树问题及其变形之间的关系，以及不同斯坦纳树变形问题之间的关系来研究斯坦纳树变形问题的近似算法，特别将考虑internal斯坦纳树问题，提出更好更有效的近似算法。