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

We describe two approximation schemes for bi-objective combinatorial optimization problems with nonnegative, integer valued objectives. The procedures compute a subset of the efficient points such that any other efficient point is within an arbitrary factor from a computed one with respect to both objectives. Both schemes are simple modifications of classical algorithms for the construction of the whole efficient set. In both procedures, a properly defined single objective subproblem has to be solved at every iteration. We show that, in both cases, the number of subproblems to be solved and the number of returned efficient points are polynomial in the input size and the reciprocal of the allowed error. We also show that a fast post-processing guarantees that the number of returned efficient points is at most three times the minimum possible number needed to approximate the efficient set within the specified tolerance. 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.