dc.contributor
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author
Serna Iglesias, María José
dc.contributor.author
Xhafa Xhafa, Fatos
dc.date.issued
1995-01-01
dc.identifier
Serna Iglesias, María José; Xhafa Xhafa, Fatos. "Parallel approximability of MAX NP problems". 1995.
dc.identifier
https://hdl.handle.net/2117/82476
dc.description.abstract
We study the relationship between the computationally defined class NCX of all optimization problems that are approximable within constant ratio in NC and syntactically defined classes MAXSNP and MAXNP. A simple observation shows that any problem in MAXSNP is constant approximable in NC. We show that MAXNP is also contained in NCX.
dc.description.abstract
Postprint (published version)
dc.format
application/postscript
dc.subject
Àrees temàtiques de la UPC::Informàtica
dc.title
Parallel approximability of MAX NP problems
dc.type
External research report
