{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T14:38:42Z","timestamp":1774881522365,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[2015,5,28]],"date-time":"2015-05-28T00:00:00Z","timestamp":1432771200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10994-015-5505-0","type":"journal-article","created":{"date-parts":[[2015,5,28]],"date-time":"2015-05-28T11:10:39Z","timestamp":1432811439000},"page":"231-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Committee polyhedral separability: complexity and polynomial approximation"],"prefix":"10.1007","volume":"101","author":[{"given":"Michael","family":"Khachay","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,5,28]]},"reference":[{"key":"5505_CR1","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1109\/TIT.1965.1053785","volume":"11","author":"C Ablow","year":"1965","unstructured":"Ablow, C., & Kaylor, D. (1965). A committee solution of the pattern recognition problem (corresp.). IEEE Transactions on Information Theory, 11, 453\u2013455.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"5505_CR2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., & Kale, S. (2012). The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8(1), 121\u2013164.","journal-title":"Theory of Computing"},{"key":"5505_CR3","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., & Safra, S. (1998). Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45, 70\u2013122.","journal-title":"Journal of the ACM"},{"key":"5505_CR4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0893-6080(05)80010-3","volume":"5","author":"A Blum","year":"1992","unstructured":"Blum, A., & Rivest, R. (1992). Training a 3-node neural network is NP-complete. Neural Networks, 5, 117\u2013127.","journal-title":"Neural Networks"},{"key":"5505_CR5","volume-title":"Convex optimization","author":"S Boyd","year":"2009","unstructured":"Boyd, S., & Vandenberghe, L. (2009). Convex optimization. Cambridge: Cambridge University Press."},{"issue":"2","key":"5505_CR6","first-page":"123","volume":"24","author":"L Breiman","year":"1996","unstructured":"Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2), 123\u2013140.","journal-title":"Machine Learning"},{"key":"5505_CR7","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1023\/A:1017934522171","volume":"45","author":"L Breiman","year":"2001","unstructured":"Breiman, L. (2001). Using iterated bagging to debias regressions. Machine Learning, 45, 261\u2013277.","journal-title":"Machine Learning"},{"key":"5505_CR8","unstructured":"Brown, G. W. (1951). Iterative solutions of games by fictitious play. In T. C. Koopmans (Ed.), Activity Analysis of Production and Allocation (pp. 374\u2013376). Cowles Commission Monograph No. 13. New York: Wiley."},{"key":"5505_CR9","first-page":"273","volume":"20","author":"C Cortes","year":"1995","unstructured":"Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20, 273\u2013297.","journal-title":"Machine Learning"},{"key":"5505_CR10","doi-asserted-by":"crossref","unstructured":"Dinur, I., Regev, O., & Smyth, C. (2002). The hardness of 3-uniform hypergraph coloring. In Proceedings of the 43rd annual IEEE symposium on founations of computer science.","DOI":"10.1109\/SFCS.2002.1181880"},{"key":"5505_CR11","unstructured":"Elster, K., Reinhardt, R., Sch\u00e4uble, M., & Donath, G. (1977). Einf\u00fchrung in die nichtlineare Optimierung. In: Mathematisch-Naturwissenschaftliche Bibliothek. BSB BG Teubner Verlagsgesellschaft Leipzig, Vol. 63."},{"key":"5505_CR12","unstructured":"Eremin, I. I. (2002). Theory of linear optimization. De Gruyter."},{"key":"5505_CR13","volume-title":"Improper linear and convex programming problems","author":"I Eremin","year":"1983","unstructured":"Eremin, I., Mazurov, V., & Astafiev, N. (1983). Improper linear and convex programming problems. Moscow: Nauka."},{"key":"5505_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U. (1998). Threshold of $$\\ln n$$ ln n for approximating set cover. Journal of the ACM, 45, 634\u2013652.","DOI":"10.1145\/285055.285059"},{"key":"5505_CR15","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1006\/inco.1995.1136","volume":"121","author":"Y Freund","year":"1995","unstructured":"Freund, Y. (1995). Boosting a weak learning algorithm by majority. Information and Computation, 121, 256\u2013285.","journal-title":"Information and Computation"},{"issue":"12","key":"5505_CR16","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1006\/game.1999.0738","volume":"29","author":"Y Freund","year":"1999","unstructured":"Freund, Y., & Schapire, R. E. (1999). Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(12), 79\u2013103.","journal-title":"Games and Economic Behavior"},{"key":"5505_CR17","first-page":"255","volume":"38","author":"D Gale","year":"1956","unstructured":"Gale, D. (1956). Neighboring vertices on a convex polyhedron. Linear inequalities and related system, 38, 255\u2013263.","journal-title":"Linear inequalities and related system"},{"key":"5505_CR18","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s00453-003-1072-z","volume":"38","author":"V Guruswami","year":"2004","unstructured":"Guruswami, V. (2004). Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Algorithmica, 38, 451\u2013469.","journal-title":"Algorithmica"},{"issue":"3","key":"5505_CR19","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1214\/009053607000000677","volume":"36","author":"T Hofmann","year":"2008","unstructured":"Hofmann, T., Sch\u00f6lkopf, B., & Smola, A. (2008). Kernel methods in machine learning. The Annals of Statistics, 36(3), 1171\u20131220.","journal-title":"The Annals of Statistics"},{"key":"5505_CR20","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1134\/S1064562406010376","volume":"73","author":"M Khachai","year":"2006","unstructured":"Khachai, M. (2006). Computational complexity of the minimum committee problem and related problems. Doklady Mathematics, 73, 138\u2013141.","journal-title":"Doklady Mathematics"},{"issue":"2","key":"5505_CR21","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1134\/S1054661808020089","volume":"18","author":"M Khachai","year":"2008","unstructured":"Khachai, M. (2008). Computational and approximational complexity of combinatorial problems related to the committee polyhedral separability of finite sets. Pattern Recognition and Image Analysis, 18(2), 236\u2013242.","journal-title":"Pattern Recognition and Image Analysis"},{"key":"5505_CR22","first-page":"S67","volume":"1","author":"M Khachai","year":"2002","unstructured":"Khachai, M., Mazurov, V., & Rybin, A. (2002). Committee constructions for solving problems of selection, diagnostics, and prediction. Proceedings of the Steklov Institute of Mathematics, 1, S67\u2013S101.","journal-title":"Proceedings of the Steklov Institute of Mathematics"},{"key":"5505_CR23","first-page":"491","volume":"8","author":"M Khachai","year":"1998","unstructured":"Khachai, M., & Rybin, A. (1998). A new estimate of the number of members in a minimum committee of a system of linear inequalities. Pattern Recgnition and Image Analysis, 8, 491\u2013496.","journal-title":"Pattern Recgnition and Image Analysis"},{"issue":"4","key":"5505_CR24","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1007\/s10852-006-9056-z","volume":"6","author":"M Khachay","year":"2007","unstructured":"Khachay, M. (2007). On the computational complexity of the minimum committee problem. Journal of Mathematical Modelling and Algorithms, 6(4), 547\u2013561.","journal-title":"Journal of Mathematical Modelling and Algorithms"},{"issue":"2","key":"5505_CR25","doi-asserted-by":"crossref","first-page":"217","DOI":"10.15388\/Informatica.2009.247","volume":"20","author":"M Khachay","year":"2009","unstructured":"Khachay, M., & Poberii, M. (2009). Complexity and approximability of committee polyhedral separability of sets in general position. Informatica, 20(2), 217\u2013234.","journal-title":"Informatica"},{"key":"5505_CR26","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1134\/S0005117912020130","volume":"73","author":"K Kobylkin","year":"2012","unstructured":"Kobylkin, K. (2012). Constraint elimination method for the committee problem. Automation and Remote Control, 73, 355\u2013368.","journal-title":"Automation and Remote Control"},{"key":"5505_CR27","first-page":"211","volume":"6","author":"J Lin","year":"1991","unstructured":"Lin, J., & Vitter, J. (1991). Complexity results on learning by neural nets. Machine Learning, 6, 211\u2013230.","journal-title":"Machine Learning"},{"key":"5505_CR28","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/inco.1994.1009","volume":"108","author":"N Littlestone","year":"1994","unstructured":"Littlestone, N., & Warmuth, M. (1994). The weighted majority algorithm. Information and Computation, 108, 212\u2013261.","journal-title":"Information and Computation"},{"key":"5505_CR29","first-page":"140","volume":"3","author":"V Mazurov","year":"1971","unstructured":"Mazurov, V. (1971). Committees of inequalities systems and the pattern recognition problem. Kibernetika, 3, 140\u2013146.","journal-title":"Kibernetika"},{"key":"5505_CR30","volume-title":"Committee method in problems of optimization and classification","author":"V Mazurov","year":"1990","unstructured":"Mazurov, V. (1990). Committee method in problems of optimization and classification. Moscow: Nauka."},{"key":"5505_CR31","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1023\/B:AURC.0000014716.77510.61","volume":"65","author":"V Mazurov","year":"2004","unstructured":"Mazurov, V., & Khachai, M. (2004). Committees of systems of linear inequalities. Automation and Remote Control, 65, 193\u2013203.","journal-title":"Automation and Remote Control"},{"key":"5505_CR32","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1134\/S0005117907050165","volume":"68","author":"V Mazurov","year":"2007","unstructured":"Mazurov, V., & Khachai, M. (2007). Parallel computations and committee constructions. Automation and Remote Control, 68, 912\u2013921.","journal-title":"Automation and Remote Control"},{"key":"5505_CR33","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF02187916","volume":"3","author":"N Megiddo","year":"1988","unstructured":"Megiddo, N. (1988). On the complexity of polyhedral separability. Discrete and Computational Geometry, 3, 325\u2013337.","journal-title":"Discrete and Computational Geometry"},{"key":"5505_CR34","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0167-6377(82)90039-6","volume":"5","author":"N Megiddo","year":"1982","unstructured":"Megiddo, N., & Tamir, A. (1982). On the complexity of locating linear facilities in the plane. Operations Research Letters, 5, 194\u2013197.","journal-title":"Operations Research Letters"},{"key":"5505_CR35","volume-title":"Learning machines: Foundations of trainable pattern classifying systems","author":"N Nilsson","year":"1965","unstructured":"Nilsson, N. (1965). Learning machines: Foundations of trainable pattern classifying systems. New York: McGraw-Hill."},{"issue":"2","key":"5505_CR36","first-page":"197","volume":"5","author":"R Schapire","year":"1990","unstructured":"Schapire, R. (1990). The strength of weak learnability. Machine Learning, 5(2), 197\u2013227.","journal-title":"Machine Learning"},{"key":"5505_CR37","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/8291.001.0001","volume-title":"Boosting: Foundations and algorithms","author":"R Schapire","year":"2012","unstructured":"Schapire, R., & Freund, Y. (2012). Boosting: Foundations and algorithms. Cambridge: MIT Press."},{"key":"5505_CR38","volume-title":"Learning with kernels: Support vector machines, regularization, optimization, and beyond","author":"B Sch\u00f6lkopf","year":"2002","unstructured":"Sch\u00f6lkopf, B., & Smola, A. (2002). Learning with kernels: Support vector machines, regularization, optimization, and beyond. Cambridge: MIT Press."},{"key":"5505_CR39","unstructured":"Syed, U. & Schapire, R. E. (2007). A game-theoretic approach to apprenticeship learning. In Advances in neural information processing systems 20, proceedings of the twenty-first annual conference on neural information processing systems, Vancouver, British Columbia, Canada (pp. 1449\u20131456) 3\u20136 December 2007."},{"issue":"2","key":"5505_CR40","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1214\/aoms\/1177730030","volume":"20","author":"A Wald","year":"1949","unstructured":"Wald, A. (1949). Statistical decision functions. The Annals of Mathematical Statistics, 20(2), 165\u2013205.","journal-title":"The Annals of Mathematical Statistics"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-015-5505-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-015-5505-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-015-5505-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T22:55:11Z","timestamp":1691708111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-015-5505-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,28]]},"references-count":40,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["5505"],"URL":"https:\/\/doi.org\/10.1007\/s10994-015-5505-0","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,28]]}}}