{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T04:13:45Z","timestamp":1782792825741,"version":"3.54.5"},"reference-count":40,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1995,8,1]],"date-time":"1995-08-01T00:00:00Z","timestamp":807235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6560,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1995,8]]},"DOI":"10.1016\/0304-3975(94)00254-g","type":"journal-article","created":{"date-parts":[[2003,4,25]],"date-time":"2003-04-25T06:09:04Z","timestamp":1051250944000},"page":"181-210","source":"Crossref","is-referenced-by-count":138,"title":["The complexity and approximability of finding maximum feasible subsystems of linear relations"],"prefix":"10.1016","volume":"147","author":[{"given":"Edoardo","family":"Amaldi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viggo","family":"Kann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(94)00254-G_BIB1","doi-asserted-by":"crossref","unstructured":"N. Alon, U. Feige, A. Wigderson and D. Zuckerman, Derandomized graph products, Comput. Complexity, to appear.","DOI":"10.1007\/BF01277956"},{"key":"10.1016\/0304-3975(94)00254-G_BIB2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0012-365X(88)90189-6","article-title":"Explicit construction of linear sized tolerant networks","volume":"72","author":"Alon","year":"1988","journal-title":"Discrete Math."},{"key":"10.1016\/0304-3975(94)00254-G_BIB3","series-title":"Artificial Neural Networks","first-page":"55","article-title":"On the complexity of training perceptrons","author":"Amaldi","year":"1991"},{"key":"10.1016\/0304-3975(94)00254-G_BIB4","author":"Amaldi","year":"1994"},{"key":"10.1016\/0304-3975(94)00254-G_BIB5","series-title":"Proc. of 34th Ann. IEEE Symp. on Foundations of Comput. Sci.","first-page":"724","article-title":"The hardness of approximate optima in lattices, codes, and systems of linear equations","author":"Arora","year":"1993"},{"key":"10.1016\/0304-3975(94)00254-G_BIB6","series-title":"Proc. of 33rd Ann. IEEE Symp. on Foundations of Comput. Sci.","first-page":"14","article-title":"Proof verification and hardness of approximation problems","author":"Arora","year":"1992"},{"key":"10.1016\/0304-3975(94)00254-G_BIB7","author":"Ausiello","year":"1994"},{"key":"10.1016\/0304-3975(94)00254-G_BIB8","series-title":"Transparent proofs and limits to approximation","author":"Babai","year":"1993"},{"key":"10.1016\/0304-3975(94)00254-G_BIB9","series-title":"Proc. Twenty fifth Ann. ACM Symp. on Theory of Comp., ACM","first-page":"294","article-title":"Efficient probabilistically checkable proofs and applications to approximation","author":"Bellare","year":"1993"},{"key":"10.1016\/0304-3975(94)00254-G_BIB10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","article-title":"On the complexity of approximating the independent set problem","volume":"96","author":"Berman","year":"1992","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(94)00254-G_BIB11","series-title":"Natural complete and intermediate problems in approximation classes","author":"Crescenzi","year":"1994"},{"key":"10.1016\/0304-3975(94)00254-G_BIB12","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","article-title":"Completeness in approximation classes","volume":"93","author":"Crescenzi","year":"1991","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(94)00254-G_BIB13","series-title":"Pattern Classification and Scene Analysis","author":"Duda","year":"1973"},{"key":"10.1016\/0304-3975(94)00254-G_BIB14","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1162\/neco.1990.2.2.198","article-title":"The upstart algorithm: a method for constructing and training feedforward neural networks","volume":"2","author":"Frean","year":"1990","journal-title":"Neural Comput."},{"key":"10.1016\/0304-3975(94)00254-G_BIB15","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1109\/72.80230","article-title":"Perceptron-based learning algorithms","volume":"1","author":"Gallant","year":"1990","journal-title":"IEEE Trans. on Neural Networks"},{"key":"10.1016\/0304-3975(94)00254-G_BIB16","author":"Garey","year":"1979"},{"key":"10.1016\/0304-3975(94)00254-G_BIB17","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1287\/ijoc.3.3.253","article-title":"Approaches to diagnosing infeasible linear programs","volume":"3","author":"Greenberg","year":"1991","journal-title":"ORSA J. Comput."},{"key":"10.1016\/0304-3975(94)00254-G_BIB18","article-title":"Trees and Hills: Methodology for Maximizing Functions of Systems of Linear Relations","volume":"Vol. 22","author":"Greer","year":"1984"},{"key":"10.1016\/0304-3975(94)00254-G_BIB19","series-title":"Discrimination and classification","author":"Hand","year":"1981"},{"key":"10.1016\/0304-3975(94)00254-G_BIB20","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0020-0190(93)90076-L","article-title":"A well-characterized approximation problem","volume":"47","author":"H\u00e5stad","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)00254-G_BIB21","author":"H\u00f6ffgen","year":"1992"},{"key":"10.1016\/0304-3975(94)00254-G_BIB22","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","volume":"9","author":"Johnson","year":"1974","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(94)00254-G_BIB23","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","article-title":"The densest hemisphere problem","volume":"6","author":"Johnson","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)00254-G_BIB24","series-title":"Proc. of 33rd Ann. IEEE Symp. on Foundations of Comput. Sci.","first-page":"296","article-title":"On the second eigenvalue and linear expansion of regular graphs","author":"Kahale","year":"1992"},{"key":"10.1016\/0304-3975(94)00254-G_BIB25","article-title":"On the approximability of NP-complete optimization problems","author":"Kann","year":"1992"},{"key":"10.1016\/0304-3975(94)00254-G_BIB26","series-title":"Proc. of 20th Internat. Colloq. on Automata, Languages and Programming","first-page":"52","article-title":"Polynomially bounded minimization problems that are hard to approximate","volume":"Vol. 700","author":"Kann","year":"1993"},{"key":"10.1016\/0304-3975(94)00254-G_BIB27","unstructured":"Nordic J. Comput., to appear."},{"key":"10.1016\/0304-3975(94)00254-G_BIB28","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","article-title":"A new polynomial time algorithm for linear programming","volume":"4","author":"Karmarkar","year":"1984","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(94)00254-G_BIB29","series-title":"Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci.","article-title":"On syntactic versus computational views of approximability","author":"Khanna","year":"1994"},{"key":"10.1016\/0304-3975(94)00254-G_BIB30","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1006\/inco.1994.1100","article-title":"Logical definability of NP optimization problems","volume":"115","author":"Kolaitis","year":"1994","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(94)00254-G_BIB31","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","article-title":"Ramanujan graphs","volume":"8","author":"Lubotzky","year":"1988","journal-title":"Combinatorica"},{"key":"10.1016\/0304-3975(94)00254-G_BIB32","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","article-title":"On the hardness of approximating minimization problems","volume":"41","author":"Lund","year":"1994","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(94)00254-G_BIB33","series-title":"Proc. of 1993 Ann. Meeting of the International Neural Network Society","first-page":"556","article-title":"An approximate algorithm to find the largest linearly separable subset of training examples","author":"Marchand","year":"1993"},{"key":"10.1016\/0304-3975(94)00254-G_BIB34","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1088\/0954-898X\/4\/1\/005","article-title":"On learning simple neural concepts: from halfspace intersections to neural decision lists","volume":"4","author":"Marchand","year":"1993","journal-title":"Network: Comput. Neural Systems"},{"key":"10.1016\/0304-3975(94)00254-G_BIB35","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1209\/0295-5075\/11\/6\/001","article-title":"A convergence theorem for sequential learning in two-layer perceptrons","volume":"11","author":"Marchand","year":"1990","journal-title":"Europhys. Lett."},{"key":"10.1016\/0304-3975(94)00254-G_BIB36","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0304-3975(93)90259-V","article-title":"Quantifiers and approximation","volume":"107","author":"Panconesi","year":"1993","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)00254-G_BIB37","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation, and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(94)00254-G_BIB38","article-title":"Theory of Linear and Integer Programming","author":"Schrijver","year":"1986"},{"key":"10.1016\/0304-3975(94)00254-G_BIB39","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1109\/T-C.1973.223652","article-title":"An algorithm for optimal solution of linear inequalities and its application to pattern recognition","volume":"22","author":"Warmack","year":"1973","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0304-3975(94)00254-G_BIB40","first-page":"475","article-title":"On the approximation of maximum satisfiability","volume":"17","author":"Yannakakis","year":"1994"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400254G?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400254G?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T03:23:25Z","timestamp":1556508205000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759400254G"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":40,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["030439759400254G"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(94)00254-g","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}