{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T17:03:25Z","timestamp":1784394205848,"version":"3.55.0"},"reference-count":66,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1998,12,1]],"date-time":"1998-12-01T00:00:00Z","timestamp":912470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1998,12,1]],"date-time":"1998-12-01T00:00:00Z","timestamp":912470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[1998,12,3]],"date-time":"1998-12-03T00:00:00Z","timestamp":912643200000},"content-version":"vor","delay-in-days":2,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1998,12]]},"DOI":"10.1016\/s0304-3975(97)00115-1","type":"journal-article","created":{"date-parts":[[2003,4,30]],"date-time":"2003-04-30T21:37:28Z","timestamp":1051738648000},"page":"237-260","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":541,"title":["On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems"],"prefix":"10.1016","volume":"209","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\/S0304-3975(97)00115-1_BIB1","series-title":"Artificial Neural Networks","first-page":"55","article-title":"On the complexity of training preceptrons","author":"Amaldi","year":"1991"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB2","series-title":"Actes du congr\u00e8s \u201cAspects th\u00e9oriques des r\u00e9seaux de neurones\u201d, Congr\u00e8s Europ\u00e9en de Math\u00e9matiques","article-title":"Complexity of problems related to training perceptrons","author":"Amaldi","year":"1992"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB3","article-title":"From finding maximum feasible subsystems of linear systems to feedforward neural network design","author":"Amaldi","year":"1994"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB4","article-title":"On the approximability of removing the smallest number of relations from linear systems to achieve feasibility","author":"Amaldi","year":"1994"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB5","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","article-title":"The complexity and approximability of finding maximum feasible subsystems of linear relations","volume":"147","author":"Amaldi","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(97)00115-1_BIB6","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/356914.356918","article-title":"Inductive inference: Theory and methods","volume":"15","author":"Angluin","year":"1983","journal-title":"ACM Comput. Surveys"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB7","series-title":"Proc. 34th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press","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\/S0304-3975(97)00115-1_BIB8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/jcss.1997.1472","article-title":"The hardness of approximate optima in lattices, codes, and systems of linear equations","author":"Arora","year":"1997","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(97)00115-1_BIB9","series-title":"Proc. 33rd Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press","first-page":"14","article-title":"Proof verification and hardness of approximation problems","author":"Arora","year":"1992"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB10","series-title":"Proc. 25th 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\/S0304-3975(97)00115-1_BIB11","series-title":"Proc. 36th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press","first-page":"422","article-title":"Free bits, PCPs and non-approximability\u2014towards tight results","author":"Bellare","year":"1995"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB12","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1080\/10556789208805504","article-title":"Robust linear programming discrimination of two linearly inseparable sets","volume":"1","author":"Bennett","year":"1992","journal-title":"Optimization Meth. Software"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB13","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02284627","article-title":"An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem","volume":"17","author":"Chinneck","year":"1996","journal-title":"Ann. Math. Artificial Intelligence"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB14","series-title":"Advances in sensitivity analysis and parametric programming","article-title":"Feasibility and viability","author":"Chinneck","year":"1997"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB15","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1287\/ijoc.3.2.157","article-title":"Locating minimal infeasible constraint sets in linear programs","volume":"3","author":"Chinneck","year":"1991","journal-title":"ORSA J. Comput."},{"key":"10.1016\/S0304-3975(97)00115-1_BIB16","series-title":"Linear programming","author":"Chvatal","year":"1983"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB17","article-title":"A compendium of NP optimization problems","author":"Crescenzi","year":"1995"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB18","series-title":"Proc. 1st Internat. Conf. on Computing and Combinatorics","first-page":"539","article-title":"Structure in approximation classes","volume":"vol. 959","author":"Crescenzi","year":"1995"},{"issue":"2","key":"10.1016\/S0304-3975(97)00115-1_BIB19","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\/S0304-3975(97)00115-1_BIB20","series-title":"Proc. 4th Israel Symp. on Theory of Computing and Systems, IEEE Comput. Soc. Press","first-page":"68","article-title":"To weight or not to weight: Where is the question?","author":"Crescenzi","year":"1996"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB21","series-title":"Pattern classification and scene analysis","author":"Duda","year":"1973"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB22","article-title":"Redundancy and Helly for linear programming","author":"Edmonds","year":"1994","journal-title":"Lecture Notes"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB23","series-title":"Proc. 4th Internat. Conf. on Integer Prog, and Combinatorial Optimization","first-page":"14","article-title":"Approximating minimum feedback sets and multi-cuts in directed graphs","volume":"vol. 920","author":"Even","year":"1995"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB24","series-title":"Proc. 28th Ann. ACM Symp. on Theory of Comp., ACM","first-page":"314","article-title":"A threshold of In n for approximating set cover","author":"Feige","year":"1996"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB25","doi-asserted-by":"crossref","first-page":"946","DOI":"10.1162\/neco.1992.4.6.946","article-title":"A thermal perceptron learning rule","volume":"4","author":"Frean","year":"1992","journal-title":"Neural Computation"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB26","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. Neural Networks"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB27","series-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB28","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1287\/ijoc.2.1.61","article-title":"Identifying minimally infeasible subsystems of inequalities","volume":"3","author":"Gleeson","year":"1990","journal-title":"ORSA J. Computing"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB29","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF02284624","article-title":"Consistency, redundancy, and implied equalities in linear systems","volume":"17","author":"Greenberg","year":"1996","journal-title":"Ann. Math. Artificial Intelligence"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB30","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. Computing"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB31","article-title":"Trees and hills: Methodology for maximizing functions of systems of linear relations","author":"Greer","year":"1984"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB32","series-title":"Proc. 2nd Internat. Conf. on Computing and Combinatorics","first-page":"273","article-title":"On the difficulty of designing good classifiers","volume":"vol. 1090","author":"Grigni","year":"1996"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB33","article-title":"Analyzing infeasible mixed-integer and integer linear programs","author":"Guieu","year":"1996"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB34","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","article-title":"Approximating the minimum maximal independence number","volume":"46","author":"Halld\u00f3roson","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(97)00115-1_BIB35","series-title":"Fundamentals of artificial neural networks","author":"Hassoun","year":"1995"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB36","series-title":"Proc. 37th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Comput. Soc. Press","first-page":"627","article-title":"Clique is hard to approximate within n1\u2212\u03b5","author":"H\u00e5stad","year":"1996"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB37","series-title":"Proc. 29th Ann. ACM Symp. on Theory of Comp, ACM","first-page":"1","article-title":"Some optimal inapproximability results","author":"H\u00e5stad","year":"1997"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB38","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1006\/jcss.1995.1011","article-title":"Robust trainability of single neurons","volume":"50","author":"H\u00f6ffgen","year":"1995","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(97)00115-1_BIB39","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\/S0304-3975(97)00115-1_BIB40","article-title":"On the Approximability of NP-complete Optimization Problems","author":"Kann","year":"1992"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB41","first-page":"317","article-title":"Polynomially bounded minimization problems that are hard to approximate","volume":"1","author":"Kann","year":"1994","journal-title":"Nordic J. Computing"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB42","series-title":"Proc. 20th Ann. Mathematical Foundations of Comput. Sci.","first-page":"227","article-title":"Strong lower bounds on the approximability of some NPO PB-complete maximization problems","volume":"vol. 969","author":"Kann","year":"1995"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB43","series-title":"Annotated Bibliographies in Combinatorial Optimization","article-title":"Hardness of approximation","author":"Kann","year":"1997"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB44","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\/S0304-3975(97)00115-1_BIB45","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/174644.174647","article-title":"Cryptographic limitations on learning boolean formulae and finite automata","volume":"41","author":"Kearns","year":"1994","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB46","series-title":"An introduction to Computational Learning Theory","author":"Kearns","year":"1994"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB47","series-title":"Proc. 12th Annual IEEE Conf. Comput. Complexity. IEEE Comput. Soc., Press","first-page":"282","article-title":"Constraint satisfaction: The approximability of minimization problems","author":"Khanna","year":"1997"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB48","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1287\/ijoc.3.4.345","article-title":"Linear discriminant functions determined by genetic search","volume":"3","author":"Koehler","year":"1991","journal-title":"ORSA J. Computing"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB49","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1111\/j.1540-5915.1990.tb00317.x","article-title":"Minimizing misclassifications in linear discriminant analysis","volume":"21","author":"Koehler","year":"1990","journal-title":"Decision Sci."},{"key":"10.1016\/S0304-3975(97)00115-1_BIB50","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1023\/A:1022657626762","article-title":"Complexity results on learning by neural nets","volume":"6","author":"Lin","year":"1991","journal-title":"Mach. Learning"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB51","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\/S0304-3975(97)00115-1_BIB52","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/BF01096681","article-title":"Misclassification minimization","volume":"5","author":"Mangasarian","year":"1994","journal-title":"J. Global Optimization"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB53","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: Computation in Neural Systems"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB54","series-title":"Discriminant analysis and statistical pattern recognition","author":"McLachlan","year":"1992"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB55","series-title":"Perceptrons: An introduction to computational Geometry","author":"Minsky","year":"1988"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB56","series-title":"Combinatorial optimization, Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB57","article-title":"A set covering approach to infeasibility analysis of linear programming problems and related issues","author":"Parker","year":"1995"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB58","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BF02284626","article-title":"Finding the minimum weight IIS cover of an infeasible system of linear inequalities","volume":"17","author":"Parker","year":"1996","journal-title":"Ann. Math. Artificial Intelligence"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB59","first-page":"717","article-title":"Cryptography","author":"Rivest","year":"1990"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB60","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0167-6377(93)90079-V","article-title":"A note on resolving infeasibility in linear programs by constraint relaxation","volume":"13","author":"Sankaran","year":"1993","journal-title":"Oper. Res. Lett."},{"key":"10.1016\/S0304-3975(97)00115-1_BIB61","article-title":"Theory of linear and integer programming","author":"Schrijver","year":"1986"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB62","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01200760","article-title":"Packing directed circuits fractionally","volume":"15","author":"Seymour","year":"1995","journal-title":"Combinatorica"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB63","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Communications of ACM"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB64","article-title":"The minimum feature set problem","author":"van Horn","year":"1992"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB65","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1016\/0893-6080(94)90082-5","article-title":"The minimum feature set problem","volume":"7","author":"van Horn","year":"1994","journal-title":"IEEE Trans. Neural Networks"},{"key":"10.1016\/S0304-3975(97)00115-1_BIB66","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."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397597001151?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397597001151?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T00:51:39Z","timestamp":1759625499000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397597001151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,12]]},"references-count":66,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1998,12]]}},"alternative-id":["S0304397597001151"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(97)00115-1","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1998,12]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/S0304-3975(97)00115-1","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1998 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}