On approximating a geometric prize-collecting traveling salesman problem with time windows

The second version deals with a general case of asymmetric distances between locations. We define a density parameter that, loosely speaking, bounds the number of zig-zags between locations within a time window. We present a dynamic programming algorithm that finds a tour that visits at least OPT/density locations during their time windows. This algorithm can be extended to deal with non-unit job profits and processing times.