A fast 4-approximation algorithm for the traveling repairman problem on a line

Author

Perez Perez, S.L. ; Urban Rivero, L.E. ; Lopez Bracho, R. ; Zaragoza Martinez, F.J.

Author_Institution

Posgrado en Optimizacion, UAM Azcapotzalco, Mexico City, Mexico

fYear

2014

fDate

Sept. 29 2014-Oct. 3 2014

Firstpage

1

Lastpage

4

Abstract

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.

Keywords

approximation theory; computational complexity; travelling salesman problems; NP-hard problem; eight-approximation algorithm; fast four-approximation algorithm; quadratic four-approximation algorithm; scheduling problem; traveling repairman problem; Algorithm design and analysis; Approximation algorithms; Approximation methods; Cities and towns; Complexity theory; Dynamic programming; Heuristic algorithms; Traveling repairman problem; approximation algorithm; scheduling problem; unit time windows;

fLanguage

English

Publisher

ieee

Conference_Titel

Electrical Engineering, Computing Science and Automatic Control (CCE), 2014 11th International Conference on

Conference_Location

Campeche

Print_ISBN

978-1-4799-6228-0

Type

conf

DOI

10.1109/ICEEE.2014.6978272

Filename

6978272