Approximation algorithms for maximum latency and partial cycle cover

AbstractWe present approximation algorithms for four variations of the maximum latency problem. We consider symmetric graphs and asymmetric graphs and both with general edge weights or weights satisfying the triangle inequality. Moreover, in each variation the starting point of the tour may either be given in the input or be a decision variable. As a tool for our solution, we use a PTAS for the maximum partial cover problem. The input to this problem is an edge weighted complete graph and an integer k, and the goal is to compute a maximum weight set of disjoint simple cycles on exactly k vertices