Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
type: Item
instance of: scholarly article
title: Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
zbMATH Open document ID: 1068.68063
author: Cristina Bazgan
author: Vangelis Th. Paschos
author: Bruno Escoffier
published in: Theoretical Computer Science
publication date: 2005-06-30T00:00:00Z
full work available at URL: https://basepub.dauphine.fr/handle/123456789/3724
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 2184101
zbMATH Keywords: Approximation algorithm
zbMATH Keywords: Approximation schema
zbMATH Keywords: Combinatorial optimization
zbMATH Keywords: Completeness
zbMATH Keywords: Complexity
zbMATH Keywords: Reduction
Wikidata QID: Q56335599
MaRDI profile type: Publication
OpenAlex ID: W1978782513
cites work: Mathematical Foundations of Computer Science 2003
cites work: COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
cites work: Q4258216
cites work: Approximate solution of NP optimization problems
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Completeness in approximation classes
cites work: On approximation scheme preserving reducibility and its applications
cites work: Bridging gap between standard and differential polynomial approximation: The case of bin-packing
cites work: Q4198056
cites work: Q4886045
cites work: On Syntactic versus Computational Views of Approximability
cites work: On the Structure of Polynomial Time Reducibility
cites work: Optimization, approximation, and complexity classes
cites work: The Traveling Salesman Problem with Distances One and Two
DOI: 10.1016/J.TCS.2005.03.007
DBLP publication ID: journals/tcs/BazganEP05
description: scientific article; zbMATH DE number 2184101