Volume 36, Number 4, October-December 2002
|Page(s)||279 - 297|
|Published online||15 July 2003|
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;
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.
Key words: Approximate algorithms / differential ratio / performance ratio / analysis of algorithms.
© EDP Sciences, 2002
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.