Learning with attribute costs

DOI10.1145/1060590.1060644MaRDI QIDQ3581435zbMATH OpenOpenAlexFDO

Authors Haim Kaplan, Eyal Kushilevitz, Yishay Mansour

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Recommendations

• scientific article; zbMATH DE number 2081009
• Evolutionary trees can be learned in polynomial time in the two-state general Markov model
• scientific article; zbMATH DE number 2019610

Cited in

(19)

• Decision trees for function evaluation: simultaneous optimization of worst and expected cost
• Learning in the presence of finitely or infinitely many irrelevant attributes
• Non-adaptive stochastic score classification and explainable halfspace evaluation
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• Optimal ordering of statistically dependent tests
• Decision tree classification with bounded number of errors
• Sequential testing in batches
• Decision-theoretic troubleshooting: hardness of approximation
• Scenario submodular cover
• A polynomial-time approximation scheme for sequential batch testing of series systems
• Max-throughput for (conservative) k-of-n testing
• Evaluation of monotone DNF formulas
• On competitive recommendations
• Adaptivity gaps for the stochastic Boolean function evaluation problem
• Simple algorithms for stochastic score classification with small approximation ratios
• An algorithm for bichromatic sorting with polylog competitive ratio
• On instance-optimal algorithms for a generalization of nuts and bolts and generalized sorting
• Non-adaptive evaluation of k-of-n functions: tight gap and a unit-cost PTAS
• The hardness of the expected decision depth problem

This page was built for publication: Learning with attribute costs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581435)