Differential approximation of NP-hard problems with equal size feasible solutions
Monnot, Jérôme (2002), Differential approximation of NP-hard problems with equal size feasible solutions, RAIRO, 36, 4, p. 279-297. http://dx.doi.org/10.1051/ro:2003008
TypeArticle accepté pour publication ou publié
MetadataShow full item record
Abstract (EN)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[t] problem): we respectively provide a 2/(t+1)- and a (t+1)/2t-standard approximation for the minimization and the maximization versions.
Subjects / Keywordsanalysis of algorithms; performance ratio; differential ratio; Approximate algorithms
Showing items related by title and author.