Decision trees for entity identification: Approximation algorithms and hardness results.
Venkatesan T. ChakaravarthyVinayaka PanditSambuddha RoyPranjal AwasthiMukesh K. MohaniaPublished in: ACM Trans. Algorithms (2011)
Keyphrases
- approximation algorithms
- entity identification
- decision trees
- np hard
- np hardness
- worst case
- special case
- text understanding
- vertex cover
- minimum cost
- training data
- document categorization
- set cover
- approximation ratio
- computational complexity
- optimal solution
- machine learning
- randomized algorithms
- naive bayes
- primal dual
- lower bound
- disjoint paths
- ensemble methods
- meta learning
- vector space model
- machine learning algorithms
- scheduling problem
- training set
- constant factor approximation