We use cookies to improve your experience with our site.
Cheng Qi, Zhu Hong. MNP: A Class of NP Optimization Problems[J]. Journal of Computer Science and Technology, 1997, 12(4): 306-313.
Citation: Cheng Qi, Zhu Hong. MNP: A Class of NP Optimization Problems[J]. Journal of Computer Science and Technology, 1997, 12(4): 306-313.

MNP: A Class of NP Optimization Problems

  • A large class of NP optimization problems called MNP are studied. It is shown that Rmax(2) is in this class and some problems which are not likely in Rmax(2) are in this class. A new kind of reductions, SL-reductions, is defined to preserve approximability and nonapprokimability, so it is a more general version of L-reductions and A-reductions. Then some complete problems of this class under SL-reductions are shown and it is proved that the max-clique problem is one of them. So all complete problems in this class are as difficult to approximate as the max-clique problem.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return