• Articles • Previous Articles     Next Articles

MNP: A Class of NP Optimization Problems

Cheng Qi; Zhu Hong;   

  1. Department of Computer Science; Fudan University; Shanghai 200433;
  • Online:1997-07-10 Published:1997-07-10

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.

Key words: data mining; association rule mining; frequent pattern mining; incremental mining;

[1] Cheng Qi, Zhu Hong. MNP: A new optimization class. In Proc. Annual Int'l Computing and Combinatorics Conf'95, Lecture Notes in Computer Science 959, pp.559-565.

[2] Karp R M. Reducibility among combinatorial problems. In Complexity of Computer Computations, Miller R E, Thatcher J W (eds.), Plenum Press, 1972.

[3] Garey M R, Johnson D S. Computers and Intractability. W. H. Freeman and Company, 1979. ……….
[1] Hui-Na Chao, Hua-Wei Li, Xiaoyu Song, Tian-Cheng Wang, Xiao-Wei Li. Evaluating and Constraining Hardware Assertions with Absent Scenarios [J]. Journal of Computer Science and Technology, 2020, 35(5): 1198-1216.
[2] De-Fu Lian, Qi Liu. Jointly Recommending Library Books and Predicting Academic Performance: A Mutual Reinforcement Perspective [J]. , 2018, 33(4): 654-667.
[3] Guo-Wei Wang, Jin-Dou Zhang, Jing Li. Complete Your Mobility: Linking Trajectories Across Heterogeneous Mobility Data Sources [J]. , 2018, 33(4): 792-806.
[4] Yu-Geng Song, Hui-Min Cui, Xiao-Bing Feng. Parallel Incremental Frequent Itemset Mining for Large Data [J]. , 2017, 32(2): 368-385.
[5] Shi-Ming Guo, Hong Gao. HUITWU: An Efficient Algorithm for High-Utility Itemset Mining in Transaction Databases [J]. , 2016, 31(4): 776-786.
[6] Ke-Yan Cao, Guo-Ren Wang, Dong-Hong Han, Guo-Hui Ding, Ai-Xia Wang, and Ling-Xu Shi. Continuous Outlier Monitoring on Uncertain Data Streams [J]. , 2014, 29(3): 436-448.
[7] Philip Leroux, Student Member, IEEE, Bart Dhoedt, Member, IEEE, Piet Demeester, Fellow, IEEE, and Filip De Turck, Senior Member, IEEE. Performance Characterization of Game Recommendation Algorithms on Online Social Network Sites [J]. , 2012, 27(3): 611-623.
[8] Jun-Qiang Liu (刘君强). Publishing Set-Valued Data Against Realistic Adversaries [J]. , 2012, 27(1): 24-36.
[9] Xiu-Li Ma (马秀莉), Hai-Feng Hu (胡海峰), Shuang-Feng Li (李双峰), Hong-Mei Xiao (肖红梅), Qiong Luo (罗琼), Dong-Qing Yang (杨冬青), Member,CCF, and Shi-Wei Tang (唐世渭), Senior Member, CCF. DHC: Distributed, Hierarchical Clustering in Sensor Networks [J]. , 2011, 26(4): 643-662.
[10] Yuan Jiang (姜远), Member, CCF, Ming Li (黎铭), Member, CCF, ACM, IEEE, and Zhi-Hua Zhou (周志华), Senior Member, CCF, IEEE, <. Software Defect Detection with ROCUS [J]. , 2011, 26(2): 328-342.
[11] Ming-Wei Zhang (张明卫), Member, CCF, Bin Zhang (张斌), Senior Member, CCF, Ying Liu (刘莹), Jun Na (那俊) and Zhi-Liang Zhu (朱志良), Senior Member, CCF. Web Service Composition Based on QoS Rules [J]. , 2010, 25(6): 1143-1156.
[12] Chong Long(龙 翀), Min-Lie Huang(黄民烈), Xiao-Yan Zhu(朱小燕), Member, CCF and Ming Li(李 明), Fellow, ACM, IEEE. A New Approach for Multi-Document Update Summarization [J]. , 2010, 25(4): 739-749.
[13] Mohamed Farouk Abdel Hady and Friedhelm Schwenker. Combining Committee-Based Semi-Supervised Learning and Active Learning [J]. , 2010, 25(4): 681-698.
[14] Charu C. Aggarwal, Member, ACM, Fellow, IEEE, Chen Chen, and Jiawei Han, Fellow, ACM, IEEE. The Inverse Classification Problem [J]. , 2010, 25(3): 458-468.
[15] Xin-Dong Wu, Senior Member, IEEE, Xing-Quan Zhu, Member, ACM, IEEE, Qi-Jun Chen, and Fei-Yue Wang, Member, ACM, Fellow, IEEE. Ubiquitous Mining with Interactive Data Mining Agents [J]. , 2009, 24(6): 1018-1027.
Full text



[1] Jin Lan; Yang Yuanyuan;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[2] Fan Zhihua;. Vectorization for Loops with Three-Forked Jumps[J]. , 1988, 3(3): 186 -202 .
[3] Guo Qingping; Y. Paker;. Communication Analysis and Granularity Assessment for a Transputer-Based System[J]. , 1990, 5(4): 347 -362 .
[4] Zhou Yong; Tang Zesheng;. Constructing Isosurfaces from 3D Data Sets Taking Account of Depth Sorting of Polyhedra[J]. , 1994, 9(2): 117 -127 .
[5] Liao Lejian; Shi Zhongzhi;. Minimal Model Semantics for Sorted Constraint Representation[J]. , 1995, 10(5): 439 -446 .
[6] Zhao Yu; Zhang Qiong; Xiang Hui; Shi Jiaosing; He Zhijun;. A Simplified Model for Generating 3D Realistic Sound in the Multimedia and Virtual Reality Systems[J]. , 1996, 11(4): 461 -470 .
[7] Wang Yun; Gu Guanqun; Dui Jiyin;. Research on Protocol Migration[J]. , 1996, 11(6): 601 -606 .
[8] Mi Thxi;. Constructive Sets in Computable Sets[J]. , 1997, 12(5): 425 -440 .
[9] CHEN Yangjun;. On the Arc Consistency Problem[J]. , 1999, 14(4): 298 -308 .
[10] WAN Yingyu; XU Yinlong; GU Xiaodong; CHEN Guoliang;. Efficient Minimum Spanning Tree Algorithms on the Reconfigurable Mesh[J]. , 2000, 15(2): 116 -125 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved