Decision trees for entity identification: approximation algorithms and hardness results.
Venkatesan T. ChakaravarthyVinayaka PanditSambuddha RoyPranjal AwasthiMukesh K. MohaniaPublished in: PODS (2007)
Keyphrases
- approximation algorithms
- entity identification
- decision trees
- np hard
- np hardness
- worst case
- text understanding
- special case
- vertex cover
- minimum cost
- computational complexity
- machine learning
- set cover
- naive bayes
- approximation ratio
- document categorization
- upper bound
- randomized algorithms
- lower bound
- polynomial time approximation
- primal dual
- training data
- machine learning algorithms
- linear programming
- constant factor
- optimal solution
- constant factor approximation
- ensemble methods
- natural language understanding
- computational linguistics
- base classifiers
- scheduling problem
- learning algorithm
- information retrieval