{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T05:16:02Z","timestamp":1740287762274,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_13","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"124-136","source":"Crossref","is-referenced-by-count":6,"title":["Poly-APX- and PTAS-Completeness in Standard and Differential Approximation"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bruno","family":"Escoffier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","volume-title":"Combinatorial optimization problems and their approximability properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. In: Combinatorial optimization problems and their approximability properties, Springer, Berlin (1999)"},{"key":"13_CR2","volume-title":"A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. In: A guide to the theory of NP-completeness, W. H. Freeman, San Francisco (1979)"},{"key":"13_CR3","unstructured":"Bazgan, C., Escoffier, B., Paschos, V.Th.:Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness. Cahier du LAMSADE 217, LAMSADE, Universit\u00e9 Paris-Dauphine, Available on (2004), http:\/\/www.lamsade.dauphine.fr\/cahiers.html"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"Crescenzi, P., Panconesi, A.: Completeness in approximation classes. Information and Computation\u00a093, 241\u2013262 (1991)","journal-title":"Information and Computation"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(94)00291-P","volume":"150","author":"G. Ausiello","year":"1995","unstructured":"Ausiello, G., Crescenzi, P., Protasi, M.: Approximate solutions of NP optimization problems. Theoret. Comput. Sci.\u00a0150, 1\u201355 (1995)","journal-title":"Theoret. Comput. Sci."},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s002249910001","volume":"33","author":"P. Crescenzi","year":"2000","unstructured":"Crescenzi, P., Trevisan, L.: On approximation scheme preserving reducibility and its applications. Theory of Computing Systems\u00a033, 1\u201316 (2000)","journal-title":"Theory of Computing Systems"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-540-45138-9_12","volume-title":"Mathematical Foundations of Computer Science 2003","author":"G. Ausiello","year":"2003","unstructured":"Ausiello, G., Bazgan, C., Demange, M., Paschos, V.Th.: Completeness in differential approximation classes. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 179\u2013188. Springer, Heidelberg (2003)"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S. Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.: On syntactic versus computational views of approximability. SIAM J\u00a028, 164\u2013191 (1998)","journal-title":"SIAM J"},{"key":"13_CR9","unstructured":"Ausiello, G., Bazgan, C., Demange, M., Paschos, V.\u00a0Th.: Completeness in differential approximation classes. Cahier du LAMSADE 204, LAMSADE, Universit\u00e9 Paris-Dauphine (2003), Available on, http:\/\/www.lamsade.dauphine.fr\/cahiers.html"},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J.\u00a0Assoc. Comput. Mach.\u00a041, 153\u2013180 (1994)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S0893-9659(99)00112-3","volume":"12","author":"M. Demange","year":"1999","unstructured":"Demange, M., Monnot, J., Paschos, V.Th.: Bridging gap between standard and differential polynomial approximation: the case of bin-packing. Appl. Math. Lett.\u00a012, 127\u2013133 (1999)","journal-title":"Appl. Math. Lett."},{"key":"13_CR12","unstructured":"Orponen, P., Mannila, H.: On approximation preserving reductions: complete problems and robust measures. Technical Report C-1987-28, Dept. of Computer Science, University of Helsinki, Finland (1987)"},{"key":"13_CR13","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proc. Symposium on Discrete Algorithms, SODA, pp. 160\u2013169 (1995)"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. In: Proc. Conference on Computational Complexity, pp. 278\u2013287 (1996)","DOI":"10.1109\/CCC.1996.507690"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T21:52:11Z","timestamp":1740261131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_13"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}