Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On parallel versus sequential approximation

Autor
Serna, M.; Xhafa, F.
Tipus d'activitat
Document cientificotècnic
Data
1995-03
Repositori
http://hdl.handle.net/2117/96432 Obrir en finestra nova
Resum
In this paper we deal with the class NCX of NP Optimization problems that are approximable within constant ratio in NC. This class is the parallel counterpart of the class APX. Our main motivation here is to reduce the study of sequential and parallel approximability to the same framework. To this aim, we first introduce a new kind of NC-reduction that preserves the relative error of the approximate solutions and show that the class NCX has {em complete} problems under this reducibility. An impo...
Citació
Serna, M., Xhafa, F. "On parallel versus sequential approximation". 1995.
Paraules clau
Optimization problems, Parallel approximation, Sequential approximation
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius