Abstract of Paper

Completeness in differential approximation classes
by Giorgio Ausiello, Cristina Bazgan, Marc Demange and Vangelis Th. Paschos

Abstract:

We study completeness in differential approximability classes. In
differential approximation, the quality of an approximation algorithm is the
measure of both how far is the solution computed from a worst one and how
close is it to an optimal one. The main classes considered are DAPX, the
differential counterpart of APX, including the NP optimization problems
approximable in polynomial time within constant differential approximation
ratio and the DGLO, the differential counterpart of GLO, including problems
for which their local optima guarantee constant differential approximation
ratio. We define natural approximation preserving reductions and prove
completeness results for the class of the NP optimization problems (class
NPO), as well as for DAPX and for a natural subclass of DGLO. We also define
class 0-APX of the NPO problems that are not differentially approximable
within any ratio strictly greater than 0 unless P =NP. This class is very
natural for differential approximation, although has no sens for the
standard one. For 0-APX also we prove completeness results under a suitably
defined reduction. Finally, we prove the existence of hard problems for
DPTAS, the class of NPO problems solvable by polynomial time differential
approximation schemata.