The Closure Class of MIN Σ0 Is NPO-PB
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.1 pp.242-246
- Publication Date
- 1997/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Algorithms and Data Structures
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takeshi OHGURO, "The Closure Class of MIN Σ0 Is NPO-PB" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 1, pp. 242-246, January 1997, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_1_242/_p
Copy
@ARTICLE{e80-a_1_242,
author={Takeshi OHGURO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Closure Class of MIN Σ0 Is NPO-PB},
year={1997},
volume={E80-A},
number={1},
pages={242-246},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - The Closure Class of MIN Σ0 Is NPO-PB
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 242
EP - 246
AU - Takeshi OHGURO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1997
AB - 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.
ER -
English
