The Closure Class of MIN Σ0 Is NPO-PB

Takeshi OHGURO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.1   pp.242-246
Publication Date: 1997/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Algorithms and Data Structures
Keyword: 
approximation,  completeness,  NPO-PB,  MIN Σ0,  

Full Text: PDF>>
Buy this Article




Summary: 
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.