For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Closure Class of MIN Σ0 Is NPO-PB
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/01/25
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Algorithms and Data Structures
approximation, completeness, NPO-PB, MIN Σ0,
Full Text: PDF>>
NPO-PB is the class of NP optimization problems with polynomially bounded values. In this paper we provide a new characterization for the class: That is, NPO-PB = MIN Σ0. This result shows that quantifiers are not relevant in characterizing approximability for minimization problems, unlike maximization problems. In proving the result, we develop a generic reduction, which combines maximization and minimization problems. Based on the new characterization, several problems are shown to be NPO-PB-complete. All of these problems are shown to be hard to approximate and tighter bounds are given.