Decision trees for entity identification

DOI10.1145/1921659.1921661zbMath1295.68210OpenAlexW1983231745MaRDI QIDQ3188997

Venkatesan T. Chakaravarthy, Vinayaka Pandit, Pranjal Awasthi, Sambuddha Roy, Mukesh Mohania

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1921659.1921661

zbMATH Keywords

Ramsey numbersdecision treeapproximation algorithms

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (11)

Decision trees for function evaluation: simultaneous optimization of worst and expected cost ⋮ Trading off worst and expected cost in decision tree problems ⋮ Approximating optimal binary decision trees ⋮ An approximation algorithm for binary searching in trees ⋮ Decision-theoretic troubleshooting: hardness of approximation ⋮ Adaptive Submodular Ranking and Routing ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Hardness and inapproximability of minimizing adaptive distinguishing sequences ⋮ On the Huffman and alphabetic tree problem with general cost functions ⋮ Average-Case Active Learning with Costs

This page was built for publication: Decision trees for entity identification