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,...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.展开更多
基金陕西省教育厅专项科研项目(The Special Foundation of Education Department of Shaanxi ProvinceChina No.07JK255)西北工业大学基础研究基金(Northwest Polytechnical University Basic Research Foundation No.W018101)
基金The National Natural Science Foundation of China grant !No.69373006 The National Hi-Tech Programme of China grant !No. 863-3
文摘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.
