Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/82476
Títol:
|
Parallel approximability of MAX NP problems
|
Autor/a:
|
Serna Iglesias, María José; Xhafa Xhafa, Fatos
|
Altres autors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
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. |
Matèries:
|
-Àrees temàtiques de la UPC::Informàtica -MAXNP -MAXSNP |
Drets:
|
|
Tipus de document:
|
Article - Versió publicada Informe |
Compartir:
|
|
Mostra el registre complet del document