Particularly, if yes then all major algorithms like Apriori, FP-Growth and Eclat are np-hard or only Apriori is np-hard?
In fact, a problem can be np-hard or not. For an algorithm, we can only say that whether it gives results in case of np-hard problems. So, there is no meaning to say that Apriori is np-hard. In fact, because some problems can not be solved within polynomial time, the words such as np-hard, np-complete etc. are introduced. The three algorithms you mentioned can be applied on any problem. But if the problem is np-hard, then it will give approximate results. So, these algorithms are called approximate algorithms. The following links will be useful. The first is a link to a good powerpoint presentation which discusses all the algorithms you mentioned. The second is a paper.
1. http://www.analysis-of-patterns.net/files/bgoethals.pdf
2. http://win.ua.ac.be/~adrem/bibrem/pubs/fimchap.pdf
Yes. Usually, we say a np-hard problem instead of a np-hard algorithm.
Okay I got the point and agree also. So may I sure that frequent itemset mining problem is np-hard or also np-complete ?
Yes, the problem is np-hard. You may be interested to refer the following paper.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.5913&rep=rep1&type=pdf
Could not retrieve this link. Can you please share title and authors so that I could get it form other sources.
The complete details of the paper is:
The Complexity of Mining Maximal Frequent Itemsets and Maximal Frequent Patterns
Guizhen Yang Department of Computer Science and Engineering University at
Buffalo, The State University of New York, Buffalo, NY14260-2000 [email protected]
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms