Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-14T04:29:58.972Z Has data issue: false hasContentIssue false

Differential approximationof NP-hard problems with equal size feasible solutions

Published online by Cambridge University Press:  15 July 2003

Jérôme Monnot*
Affiliation:
LAMSADE, Université Paris-Dauphine, place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France; monnot@lamsade.dauphine.fr.
Get access

Abstract

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

Information

Type
Research Article
Copyright
© EDP Sciences, 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable