Approximation schemes for bi-objective combinatorial optimization and their application to the TSP with profits

We test the procedures on the Traveling Salesman Problem with Profits, where profits and costs are treated as conflicting objectives. Results are taken on randomly generated instances and on TSPLIB instances. We show that both algorithms return a guaranteed approximation with significant time sparing with respect to exact procedures. We also give empirical evidence that in the specific application the number of points returned by the approximation schemes is close to the minimum.