The Closure Class of MIN Σ_0 Is NPO-PB

スポンサーリンク

概要

• 論文の詳細を見る

• NPO-P B 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.

• 社団法人電子情報通信学会の論文
• 1997-01-25

著者

• Ohguro Takeshi

  Computer Science Laboratory Ntt Cs Labs.

関連論文

• The Closure Class of MIN Σ_0 Is NPO-PB

スポンサーリンク