Differential approximation of NP-hard problems with equal size feasible solutions

LAMSADE, Université Paris-Dauphine, place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France; monnot@lamsade.dauphine.fr.

Received: October 2002

Abstract

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties; most of these are deduced from the equivalence, under differential approximation, between two versions of a problem π which only differ on a linear transformation of their objective functions. This is notably the case of maximization and minimization versions of π, as well as general minimization and minimization with triangular inequality versions of π. Then, we prove that some well known problems do belong to this class, such as special cases of both spanning tree and vehicles routing problems. In particular, we study the strict rural postman problem (called SRPP) and show that both the maximization and the minimization versions can be approximately solved, in polynomial time, within a differential ratio bounded above by 1/2. From these results, we derive new bounds for standard ratio when restricting edge weights to the interval [a,ta] (the SRPP[t] problem): we respectively provide a 2/(t+1)- and a (t+1)/2t-standard approximation for the minimization and the maximization versions.