Approximation Algorithms for the Street Sweeping Problem

被引：0
作者：
Hernandez Sanchez, L. F. [1 ]
Chavez Lomeli, L. E. [2 ]
Zaragoza Martinez, F. J. [3 ]
机构：
[1] UAM Azcapotzalco, Posgrad Optimizac, Mexico City, DF, Mexico
[2] UAM Azcapotzalco, Dept Ciencias Basicas, Mexico City, DF, Mexico
[3] UAM Azcapotzalco, Dept Sistemas, Mexico City, DF, Mexico
来源：
2014 11TH INTERNATIONAL CONFERENCE ON ELECTRICAL ENGINEERING, COMPUTING SCIENCE AND AUTOMATIC CONTROL (CCE) | 2014年
关键词：
windy postman problem; street sweeping problem; approximation algorithms; POSTMAN PROBLEM; GRAPHS;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The Street sweeping problem (SSP) is a variation of the Windy postman problem (WPP) in which we must construct two tours traversing every edge, and each edge must be traversed once in each direction: one on the first tour and the opposite in the second tour. The computational complexity of this problem remains open. We present a (3/2 alpha vertical bar 1) -approximation algorithm for the SSP using an alpha-approximation algorithm for the WPP. We also present exact algorithms for some classes of graphs.
引用
收藏
页数：4
相关论文
共 8 条
1