A Fast 4-Approximation Algorithm for the Traveling Repairman Problem on a Line

被引：0
作者：
Perez Perez, S. L. [1 ,3 ]
Urban Riverol, L. E. [1 ]
Lopez Bracho, R. [2 ]
Zaragoza Martinez, F. J. [2 ]
机构：
[1] UAM Azcapotzalco, Posgrad Optimizac, Mexico City, DF, Mexico
[2] UAM Azcapotzalco, Dept Sistemas, Mexico City, DF, Mexico
[3] UAM Cuajimalpa, Dept Tecnol Informac, Mexico City, DF, Mexico
来源：
2014 11TH INTERNATIONAL CONFERENCE ON ELECTRICAL ENGINEERING, COMPUTING SCIENCE AND AUTOMATIC CONTROL (CCE) | 2014年
关键词：
Traveling repairman problem; scheduling problem; unit time windows; approximation algorithm; SPEEDING DELIVERYMAN PROBLEMS; TIME WINDOWS; APPROXIMATION ALGORITHMS; SALESMAN;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The traveling repairman problem is a scheduling problem in which a repairman is supposed to visit some customers at their locations to perform some jobs. Each customer has a time window during which the repairman is allowed to arrive to perform the jobs. The goal is to maximize the number of visited locations. In this work we deal with a special case in which the locations are on a line, the processing time of each job is zero, and the time window length is unitary. Although the general TRP is NP-Hard, the complexity of this special case remains unknown. We introduce a quadratic 4-approximation algorithm based on the 8-approximation algorithm proposed in 2005 by R. Bar-Yehuda, G. Even, and S. Shahar.
引用
收藏
页数：4
相关论文
共 5 条
1