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

Monnot, Jérôme

RAIRO - Operations Research - Recherche Opérationnelle, Tome 36 (2002) no. 4, pp. 279-297

Résumé

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 $\pi$ which only differ on a linear transformation of their objective functions. This is notably the case of maximization and minimization versions of $\pi$, as well as general minimization and minimization with triangular inequality versions of $\pi$. 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\left[t\right]$ problem): we respectively provide a $2/(t+1)$- and a $(t+1)/2t$-standard approximation for the minimization and the maximization versions.

Détail

DOI : 10.1051/ro:2003008

Keywords: approximate algorithms, differential ratio, performance ratio, analysis of algorithms