EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO Oper. Res.
Volume 36, Number 4, October-December 2002
Page(s) 279 - 297
DOI 10.1051/ro:2003008

RAIRO Oper. Res. 36 (2002) 279-297
DOI: 10.1051/ro:2003008

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

Jérôme Monnot

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  $\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.


Key words: Approximate algorithms, differential ratio, performance ratio, analysis of algorithms.


© EDP Sciences 2002


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.