Loading...
Loading...

Go to the content (press return)

On parallel versus sequential approximation

Author
Serna, M.; Xhafa, F.
Type of activity
Report
Date
1995-03
Repository
http://hdl.handle.net/2117/96432 Open in new window
Abstract
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...
Citation
Serna, M., Xhafa, F. "On parallel versus sequential approximation". 1995.
Keywords
Optimization problems, Parallel approximation, Sequential approximation
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments