Approximation Algorithms for Some Graph Routing Problems

论文摘要

图路由问题近几年来一直都是计算机科学和组合优化领域中的热门问题。很多学者都对旅行商推广和变形问题做了深入的研究。在本文中,我们研究的是著名的旅行商问题(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’至少一次,并且总权重达到最小。对于这个问题,每个聚类只能遍历一次。针对于起始点和终止点是否确定,我们把这个问题分成两类。当聚类内部的起始点和终止点都确定时,我们给出一个近似比为3.1的近似算法。当每个聚类内部没有确定起始点和终止点时,针对于必过边是否完全分布在各个聚类当中,我们把这个情况分为两个子情况。当所有的必过边都在聚类内部时,我们给出了一个近似比为3.25的近似算法,当聚类与聚类之间存在必过边时,我们给出了一个近似比为2.25的近似算法。

论文目录

• 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

文章来源

类型: 硕士论文

作者: 明巧霞

导师: 张晓岩

关键词: 旅行商问题,聚类旅行商问题,近似算法,一般路由问题

来源: 南京师范大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 南京师范大学

分类号: O157.5;TP301.6

DOI: 10.27245/d.cnki.gnjsu.2019.000944

总页数: 52

文件大小: 2521K

下载量: 13