{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T07:10:21Z","timestamp":1737097821013,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540412373"},{"type":"electronic","value":"9783540409922"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40992-0_17","type":"book-chapter","created":{"date-parts":[[2007,6,13]],"date-time":"2007-06-13T00:01:19Z","timestamp":1181692879000},"page":"224-238","source":"Crossref","is-referenced-by-count":2,"title":["Sharper Bounds for the Hardness of Prototype and Feature Selection"],"prefix":"10.1007","author":[{"given":"Richard","family":"Nock","sequence":"first","affiliation":[]},{"given":"Marc","family":"Sebban","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,10,19]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, Marchetti Spaccamela A., and Protasi M. Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, Berlin, 1999. 226","DOI":"10.1007\/978-3-642-58412-1"},{"key":"17_CR2","unstructured":"S. Arora. Probabilistic checking of proofs and hardness of approximation problems. Technical Report CS-TR-476-94, Princeton University, 1994. 225, 228"},{"key":"17_CR3","first-page":"228","volume":"225","author":"M. Bellare","year":"1996","unstructured":"M. Bellare. Proof checking and Approximation: towards tight results. SIGACT news, 1996. 225, 228","journal-title":"SIGACT news"},{"key":"17_CR4","unstructured":"L. Breiman, J. H. Freidman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984. 227"},{"key":"17_CR5","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0004-3702(97)00063-5","volume":"225","author":"A. Blum","year":"1997","unstructured":"A. Blum and P. Langley. Selection of relevant features and examples in machine learning. Artificial Intelligence, pages 245\u2013272, 1997. 225, 227, 235","journal-title":"Artificial Intelligence"},{"key":"17_CR6","unstructured":"A. Blum. Relevant examples and relevant features: Thoughts from computational learning theory. In AAAI Fall Symposium (survey paper), 1994. 224"},{"key":"17_CR7","unstructured":"P. Crescenzi and V. Kann. A Compendium of NP-Optimization problems. WWW-Available at http:\/\/www.nada.kth.se\/~viggo\/wwwcompendium\/ , 2000. 226, 230"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"T. Hancock, T. Jiang, M. Li, and J. Tromp. Lower bounds on learning decision lists and trees. In Proc. of the Symposium on Theoretical Aspects of Computer Science, 1994. 225, 231","DOI":"10.1007\/3-540-59042-0_102"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"L. Hyafil and R. Rivest. Constructing optimal decision trees is npcomplete. Inform. Process. Letters, pages 15\u201317, 1976. 231","DOI":"10.1016\/0020-0190(76)90095-8"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"George H. John, Ron Kohavi, and Karl Pfleger. Irrelevant features and the subset selection problem. In Proc. of the 11 th International Conference on Machine Learning, pages 121\u2013129, 1994. 233","DOI":"10.1016\/B978-1-55860-335-6.50023-4"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"D. S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sci., pages 256\u2013278, 1974. 226, 235","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"17_CR12","first-page":"225","volume":"2","author":"V. Kann","year":"1997","unstructured":"V. Kann, S. Khanna, J. Lagergren, and A. Panconesi. On the hardness of approximating MAX k-CUT and its dual. Chicago Journal of Theoretical Computer Science, 2, 1997. 225","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"M.J. Kearns and Y. Mansour. On the boosting ability of top-down decision tree learning algorithms. Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 459\u2013468, 1996. 227","DOI":"10.1145\/237814.237994"},{"key":"17_CR14","unstructured":"R. Kohavi. Feature subset selection as search with probabilistic estimates. In AAAI Fall Symposium on Relevance, 1994. 224"},{"key":"17_CR15","unstructured":"R. Kohavi and D. Sommerfield. Feature subset selection using the wrapper model: overfitting and dynamic search space topology. In First International Conference on Knowledge Discovery and Data Mining, 1995. 224"},{"key":"17_CR16","unstructured":"D. Koller and R. M. Sahami. Toward optimal feature selection. In Proc. of the 13 th International Conference on Machine Learning, 1996. 224"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"M. J. Kearns and U. V. Vazirani.An Introduction to Computational Learning Theory. M.I.T. Press, 1994. 231, 235","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"17_CR18","unstructured":"T. Mitchell. Machine Learning. McGraw-Hill, 1997. 227"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"R. Nock and O. Gascuel. On learning decision committees. In Proc. of the 12 th International Conference on Machine Learning, pages 413\u2013420, 1995. 231","DOI":"10.1016\/B978-1-55860-377-6.50058-X"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"R. Nock and P. Jappy. Function-free horn clauses are hard to approximate. In Proc. of the Eighth International Conference on Inductive Logic Programming, pages 195\u2013204, 1998. 225","DOI":"10.1007\/BFb0027323"},{"key":"17_CR21","unstructured":"R. Nock and P. Jappy. On the power of decision lists. In Proc. of the 15 th International Conference on Machine Learning, pages 413\u2013420, 1998. 231"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"R. Nock, P. Jappy, and J. Sallantin. Generalized Graph Colorability and Compressibility of Boolean Formulae. In Proc. of the 9 th International Symp. on Algorithms and Computation, pages 237\u2013246, 1998. 225, 226, 231","DOI":"10.1007\/3-540-49381-6_26"},{"key":"17_CR23","unstructured":"R. Nock. Learning logical formulae having limited size: theoretical aspects, methods and results. PhD thesis, Universit\u00e9 Montpellier II, 1998. Also available as techreport RR-LIRMM-98014. 231"},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"K. Pillaipakkamnatt and V. Raghavan. On the limits of proper learnability of subclasses of DNF formulae. In Proc. of the 7 th International Conference on Computational Learning Theory, pages 118\u2013129, 1994. 232","DOI":"10.1145\/180139.181063"},{"key":"17_CR25","unstructured":"J. R. Quinlan. C4.5: programs for machine learning. Morgan Kaufmann, 1994. 227"},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"D. B. Skalak. Prototype and feature selection by sampling and random mutation hill-climbing algorithms. In Eleventh International Conference on Machine Learning, pages 293\u2013301, 1994. 224","DOI":"10.1016\/B978-1-55860-335-6.50043-X"},{"key":"17_CR27","unstructured":"M. Sebban and R. Nock. Combining feature and prototype pruning by uncertainty minimization. In Proc. of the 16 th International Conference on Uncertainty in Artificial Intelligence, 2000. to appear. 224"},{"key":"17_CR28","unstructured":"M. Sebban and R. Nock. Prototype selection as an information-preserving problem. In Proc. of the 17 th International Conference on Machine Learning, 2000. to appear. 224"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"R. E. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions. In Proceedings of the Eleventh Annual ACM Conference on Computational Learning Theory, pages 80\u201391, 1998. 227","DOI":"10.1145\/279943.279960"},{"key":"17_CR30","unstructured":"D. Wilson and T. Martinez. Instance pruning techniques. In Proc. of the 14 th International Conference on Machine Learning, pages 404\u2013411, 1997. 224"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40992-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T06:43:48Z","timestamp":1737096228000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40992-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412373","9783540409922"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-40992-0_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}