Approximation Algorithms for Some Graph Routing Problems

发布时间：2021-04-15 08:47

　　图路由问题近几年来一直都是计算机科学和组合优化领域中的热门问题。很多学者都对旅行商推广和变形问题做了深入的研究。在本文中,我们研究的是著名的旅行商问题（TSP）的两个推广问题。第一个问题我们研究的带罚的聚类旅行商问题:给定一个完全无向图G=（V,E）,V表示顶点集合,E表示边集合,并且边权重c（e）满足三角不等式。顶点集合V被划分为k个聚类,并且每个聚类的起始点si和终止点ti都已经确定。对于每一个聚类i而言,都存在一个罚值πi,这个问题的目标是找一个环游使得经过的聚类的总权重和不在环游上的聚类的罚函数值的总和达到最小。对于这个问题,我们给出了一个近似比为25/6的近似算法。第二个问题是一般聚类路由问题,在这个问题中,给定完全图G=（V,E）,V表示顶点集合,E表示边集合。其中顶点集被划分为C1,…,Ck个聚类。V’（?）V和E’（?）E分别是初始给定的必过点子集和必过边子集。并且边权重l（e）满足三角不等式。这个问题的目标是找到一个环游使得经过必过点V’仅一次,经过必过边E’至少一次,并且总权重达到最小。对于这个问题,每个聚类只能遍历一次。针对于起始点和终止点是否确定,我们把这个问题... 

【文章来源】：南京师范大学江苏省 211工程院校

【文章页数】：52 页

【学位级别】：硕士

【文章目录】：
Abstract （in English）
Abstract （in Chinese）
Chapter 1 Introduction
    1.1 The background of routing problem and its generations
    1.2 Basic definitions
    1.3 Our results
    1.4 Organization of the thesis
Chapter 2 Basic Algorithm and Preliminary Work
    2.1 Christofides' algorithm for TSP
    2.2 Short-cut algorithm
    2.3 Three subproblems and corresponding algorithms
        2.3.1 The Travelling Salesman Path Problem
        2.3.2 The Stacker Crane Problem
        2.3.3 The Rural Postman Problem
Chapter 3 The Prize-collecting Cluster Travelling Salesman Problem
    3.1 Introduction of the prize-collecting cluster traveling salesman problem
        3.1.1 Basic knowledge
        3.1.2 The algorithm and its analysis
Chapter 4 The Cluster General Routing Problem
    4.1 The cluster general routing problem with specified end vertices
        4.1.1 The algorithm and its analysis
    4.2 The cluster general routing problem with unspecified end vertices
        4.2.1 The algorithm and its analysis
Chapter 5 Conclusion
Bibliography
Acknowledgements



本文编号：3139015