Paper Info
Title
3-approximation Algorithm for the Travelling Repairman Problem with Unit Time-windows.
Abstract
The travelling repairman problem (TRP) is a scheduling problem in which a repairman must visit locations to perform some task. Each location has a time window in which the repairman is allowed to arrive. The objective of this problem is to maximize the number of tasks performed. In this paper, we consider a special case in which all the locations are on a straight line, the tasks have no processing time, and all time-windows are of unit length. We present an improvement on the analysis of the 4-approximation algorithm presented by S. L. P erez P erez et al. in 2014.
Year
Venue
Field
2015
Research in Computing Science
Approximation algorithm,Line (geometry),Mathematical optimization,Job shop scheduling,Computer science,Special case
DocType
Volume
Citations 
Journal
107
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Luis Eduardo Urbán Rivero100.68
Cynthia A. Rodríguez Villalobos200.34
Rafael López-Bracho300.68
Francisco Javier Zaragoza Martínez401.35