World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES

    https://doi.org/10.1142/S0129054105003807Cited by:9 (Source: Crossref)

    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. We define natural reductions preserving approximation and prove completeness results for the class of the NP optimization problems (class NPO), as well as for DAPX, the differential counterpart of APX, and for a natural subclass of DGLO, the differential counterpart of GLO. 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 sense for the standard one. Finally, we prove the existence of hard problems for a subclass of DPTAS, the differential counterpart of PTAS.

    References

    • A. Aielloet al., Algebra, combinatorics, and logic in computer science I, ed. C. M. S. J. Bolyai (North-Holland, New York, 1986) pp. 51–62. Google Scholar
    • S. Arora and C. Lund, Approximation algorithms for NP-hard problems, ed. D. S. Hochbaum (PWS, Boston, 1997) pp. 399–446. Google Scholar
    • G.   Ausiello et al. , Complexity and approximation. Combinatorial optimization problems and their approximability properties ( Springer , Berlin , 1999 ) . Google Scholar
    • G. Ausiello, P. Crescenzi and M. Protasi, Theoret. Comput. Sci. 150, 1 (1995). Crossref, Web of ScienceGoogle Scholar
    • G. Ausiello, A. D'Atri and M. Protasi, On the structure of combinatorial problems and structure preserving reductions, Proc. ICALP'77 (Springer-Verlag, 1977) pp. 45–60. Google Scholar
    • G. Ausiello, A. D'Atri and M. Protasi, J. Comput. System Sci. 21, 136 (1980). Crossref, Web of ScienceGoogle Scholar
    • G. Ausiello and M. Protasi, Inform. Process. Lett. 54(2), 73 (1995). Crossref, Web of ScienceGoogle Scholar
    • G. Ausiello and M. Protasi, Combinatorics and applications. Proc. 7th Quadriennal International Conference on the Theory and Applications of Graphs 2, eds. Y. Alavi and A. Schwenk (1995) pp. 957–975. Google Scholar
    • C. Bazgan and V. T. Paschos, European J. Oper. Res. 147(2), 397 (2003). Crossref, Web of ScienceGoogle Scholar
    • S. A. Cook, The complexity of theorem-proving procedures, Proc. STOC'71 (1971) pp. 151–158. Google Scholar
    • P. Crescenziet al., SIAM J. Comput. 28(5), 1759 (1999). Crossref, Web of ScienceGoogle Scholar
    • P. Crescenzi and A. Panconesi, Information and Computation 93(2), 241 (1991). Crossref, Web of ScienceGoogle Scholar
    • P. Crescenzi and L. Trevisan, Theory of Computing Systems 33(1), 1 (2000). Crossref, Web of ScienceGoogle Scholar
    • M. Demange, P. Grisoni and V. Paschos, Theoret. Comput. Sci. 209, 107 (1998). Crossref, Web of ScienceGoogle Scholar
    • M. Demange and V. Paschos, C. R. Acad. Sci. Paris Sér. I Math. 317, 409 (1993). Google Scholar
    • M. Demange and V. Paschos, Theoret. Comput. Sci. 158, 117 (1996). Crossref, Web of ScienceGoogle Scholar
    • R. Hassin and S. Khuller, J. Algorithms 41, 429 (2001). Crossref, Web of ScienceGoogle Scholar
    • S. Khannaet al., SIAM J. Comput. 28, 164 (1998). Crossref, Web of ScienceGoogle Scholar
    • J. Monnot, Inform. Process. Lett. 82(5), 229 (2002). Crossref, Web of ScienceGoogle Scholar
    • J. Monnot, V. Paschos, and S. Toulouse. Optima locaux garantis pour l'approximation différentielle. Cahier du LAMSADE 203, LAMSADE, Université Paris-Dauphine, 2002. Available on http://www.lamsade.dauphine.fr/cahdoc.html#cahiers . Google Scholar
    • J. Monnot, V. Paschos and S. Toulouse, Mathematical Methods of Operations Research 57(1), 387 (2003). Google Scholar
    • P. Orponen and H. Mannila. On approximation preserving reductions: complete problems and robust measures. Technical Report C-1987-28, Dept. of Computer Science, University of Helsinki, Finland, 1987 . Google Scholar
    • C. H. Papadimitriou and M. Yannakakis, J. Comput. System Sci. 43, 425 (1991). Crossref, Web of ScienceGoogle Scholar
    • S. Toulouse. Approximation polynomiale: optima locaux et rapport différentiel. Thèse de doctorat, LAMSADE, Université Paris-Dauphine, 2001 . Google Scholar
    • V.   Vazirani , Approximation algorithms ( Springer , Berlin , 2001 ) . Google Scholar
    • E. Zemel, Math. Oper. Res. 6, 319 (1981). Crossref, Web of ScienceGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science