| 混合图上最小-最大圈覆盖问题的近似算法 |
| |
| 引用本文： | 包晓光,路超,黄冬梅,余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113. DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.010 |
| |
| 作者姓名： | 包晓光 路超 黄冬梅 余炜 |
| |
| 作者单位： | 1. 上海海洋大学信息学院, 上海 201306;2. 上海电力大学, 上海 200090;3. 华东理工大学理学院, 上海 200237 |
| |
| 基金项目： | 国家自然科学基金(Nos.11701363,41671431);上海市自然科学基金(No.19ZR1411800)。 |
| |
| 摘 要： | 考虑一个混合图上的最小-最大圈覆盖问题.给定一个正整数k和一个混合加权图G=(V E,A),这里V表示顶点集,E表示边集,A表示弧集.E中的每条边和A中的每条弧关联一个权重.问题的要求是确定k个环游,使得这k个环游能够经过A中的所有弧.目标是极小化最大环游的权重.该问题是运筹学和计算机科学中一个重要的组合优化问题,它和...
|
| 关 键 词： | 近似算法 混合图 最小-最大 圈覆盖 乡村邮递员问题 中国邮递员问题 旅行商问题 |
| 收稿时间： | 2020-01-02 |
Approximation algorithm for min-max cycle cover problem on a mixed graph |
| |
| BAO Xiaoguang,LU Chao,HUANG Dongmei,YU Wei. Approximation algorithm for min-max cycle cover problem on a mixed graph[J]. OR Transactions, 2021, 25(1): 107-113. DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.010 |
| |
| Authors: | BAO Xiaoguang LU Chao HUANG Dongmei YU Wei |
| |
| Affiliation: | 1. College of Information Technology, Shanghai Ocean University, Shanghai 201306, China;2. Shanghai University of Electric Power, Shanghai 200090, China;3. School of Science, East China University of Science and Technology, Shanghai 200237, China |
| |
| Abstract: | We consider a min-max cycle cover problem,in which we are given a positive integer k and a mixed weighted graph G=(V,E,A)with vertex set V,edge set E and arc set A.Each edge in E and each arc in A is associated a weight,respectively.The problem is to determine k tours such that the k tours pass through all the arcs in A.The objective is to minimize the weight of the maximum weight tour.The problem is an important combinatorial optimization problem in operations research and computer science.This problem and its variants are widely used in related industries such as express delivery,trash collection,snow removal,etc.For the problem,we propose the first constant-factor approximation algorithm with ratio 37/5 by using binary search and tour splitting techniques. |
| |
| Keywords: | approximation algorithm mixed graph min-max cycle cover rural postman problem Chinese postman problem traveling salesman problem |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
|
