{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T01:51:18Z","timestamp":1751939478398},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s0129054105003807","type":"journal-article","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T06:54:25Z","timestamp":1133506465000},"page":"1267-1295","source":"Crossref","is-referenced-by-count":10,"title":["COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES"],"prefix":"10.1142","volume":"16","author":[{"given":"GIORGIO","family":"AUSIELLO","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica e  Sistemistica, Universit\u00e0 degli Studi di Roma \"La Sapienza\",  Via salaria 113, 00198, Roma, Italy"}]},{"given":"CRISTINA","family":"BAZGAN","sequence":"additional","affiliation":[{"name":"LAMSADE (Laboratoire d'Analyse et  Mod\u00e9lisation de Syst\u00e8mes pour l'Aide \u00e0  la D\u00e9cision.), CNRS UMR 7024 and Universit\u00e9  Paris-Dauphine, Place du Mar\u00e9chal De Lattre de Tassigny,  75775 Paris Cedex 16, France"}]},{"given":"MARC","family":"DEMANGE","sequence":"additional","affiliation":[{"name":"Department of Decision and  Information Systems, ESSEC, France"}]},{"given":"VANGELIS TH.","family":"PASCHOS","sequence":"additional","affiliation":[{"name":"LAMSADE, CNRS UMR 7024 and  Universit\u00e9 Paris-Dauphine, Place du Mar\u00e9chal  De Lattre de Tassigny, 75775 Paris Cedex 16, France"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","unstructured":"A.\u00a0Aiello, Algebra, combinatorics, and logic in computer science\u00a0I, ed. C. M. S. J.\u00a0Bolyai (North-Holland, New York, 1986)\u00a0pp. 51\u201362."},{"key":"rf2","unstructured":"S.\u00a0Arora and C.\u00a0Lund, Approximation algorithms for NP-hard problems, ed. D. S.\u00a0Hochbaum (PWS, Boston, 1997)\u00a0pp. 399\u2013446."},{"key":"rf3","volume-title":"Complexity and approximation. Combinatorial optimization problems and their approximability properties","author":"Ausiello G.","year":"1999"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00291-P"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90046-X"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00006-X"},{"key":"rf8","unstructured":"G.\u00a0Ausiello and M.\u00a0Protasi, Combinatorics and applications. Proc. 7th Quadriennal International Conference on the Theory and Applications of Graphs\u00a02, eds. Y.\u00a0Alavi and A.\u00a0Schwenk (1995)\u00a0pp. 957\u2013975."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00299-0"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796304220"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90025-W"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910001"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00099-6"},{"key":"rf15","first-page":"409","volume":"317","author":"Demange M.","journal-title":"C. R. Acad. Sci. Paris S\u00e9r. I Math."},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00060-7"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1187"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795286612"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00287-3"},{"key":"rf21","first-page":"387","volume":"57","author":"Monnot J.","journal-title":"Mathematical Methods of Operations Research"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"rf25","volume-title":"Approximation algorithms","author":"Vazirani V.","year":"2001"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.3.319"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003807","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:29:23Z","timestamp":1565177363000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003807"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":21,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0129054105003807"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003807","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}