{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:10:38Z","timestamp":1759666238743},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540660194"},{"type":"electronic","value":"9783540487777"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"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":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48777-8_4","type":"book-chapter","created":{"date-parts":[[2007,3,2]],"date-time":"2007-03-02T13:43:11Z","timestamp":1172842991000},"page":"45-59","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Some Structural and Algorithmic Properties of the Maximum Feasible Subsystem Problem"],"prefix":"10.1007","author":[{"given":"Edoardo","family":"Amaldi","sequence":"first","affiliation":[]},{"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[]},{"suffix":"Jr.","given":"Leslie E.","family":"Trotter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1999,4,30]]},"reference":[{"key":"4_CR1","first-page":"263","volume":"81","author":"C. C. Aggarwal","year":"1998","unstructured":"C. C. Aggarwal, R. K. Ahuja, J. Hao, and J. B. Orlin, Diagnosing infeasibilities in network flow problems, Mathematical Programming, 81 (1998), pp. 263\u2013280.","journal-title":"Mathematical Programming"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"E. Amaldi, From finding maximum feasible subsystems of linear systems to feed-forward neural network design, PhD thesis, Dep. of Mathematics, EPF-Lausanne, 1994.","DOI":"10.1007\/3-540-57785-8_168"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","volume":"147","author":"E. Amaldi","year":"1995","unstructured":"E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations, Theoretical Comput. Sci., 147 (1995), pp. 181\u2013210.","journal-title":"Theoretical Comput. Sci."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(97)00115-1","volume":"209","author":"E. Amaldi","year":"1998","unstructured":"\u2014, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Theoretical Comput. Sci., 209 (1998), pp. 237\u2013260.","journal-title":"Theoretical Comput. Sci."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, J. Comput. Syst. Sci., 54 (1997), pp. 317\u2013331.","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR6","unstructured":"A. Bachem and M. Gr\u00f6tschel, New aspects of polyhedral theory, in Optimization and Operations Research, A. Bachem, ed., Modern Applied Mathematics, North Holland, 1982, ch. I.2, pp. 51\u2013106."},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01582278","volume":"43","author":"E. Balas","year":"1989","unstructured":"E. Balas and S. M. Ng, On the set covering polytope: All the facets with coefficients in {0,1,2}, Mathematical Programming, 43 (1989), pp. 57\u201369.","journal-title":"Mathematical Programming"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"4_CR9","unstructured":"J. Bokowski and B. Sturmfels, Computational Synthetic Geometry, no. 1355 in Lecture Notes in Mathematics, Springer-Verlag, 1989."},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0377-2217(94)90152-X","volume":"73","author":"N. Chakravarti","year":"1994","unstructured":"N. Chakravarti, Some results concerning post-infeasibility analysis, Eur. J. Oper. Res., 73 (1994), pp. 139\u2013143.","journal-title":"Eur. J. Oper. Res."},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1057\/palgrave.jors.0470106","volume":"47","author":"J. Chinneck","year":"1996","unstructured":"J. Chinneck, Computer codes for the analysis of infeasible linear programs, J. Oper. Res. Soc., 47 (1996), pp. 61\u201372.","journal-title":"J. Oper. Res. Soc."},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02284627","volume":"17","author":"J. Chinneck","year":"1996","unstructured":"\u2014, An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem, Annals of Mathematics and Artificial Intelligence, 17 (1996), pp. 127\u2013144.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR13","unstructured":"\u2014, Feasibility and viability, in Advances in Sensitivity Analysis and Parametric Programming, T. G\u00e1l and H. Greenberg, eds., Kluwer Academic Publishers, 1997."},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1287\/ijoc.3.2.157","volume":"3","author":"J. Chinneck","year":"1991","unstructured":"J. Chinneck and E. Dravnieks, Locating minimal infeasible constraint sets in linear programs, ORSA Journal on Computing, 3 (1991), pp. 157\u2013168.","journal-title":"ORSA Journal on Computing"},{"key":"4_CR15","unstructured":"M. Dell\u2019amico, F. Maffioli, and S. Martello, Annotated Bibliographies in Combinatorial Optimization, John Wiley, 1997."},{"key":"4_CR16","series-title":"Annals of Mathematical Studies","first-page":"99","volume-title":"Linear Inequalities and Related Systems","author":"K. Fan","year":"1956","unstructured":"K. Fan, On systems of linear inequalities, in Linear Inequalities and Related Systems, H. W. KUHN and A. W. TUCKER, eds., no. 38 in Annals of Mathematical Studies, Princeton University Press, NJ, 1956, pp. 99\u2013156."},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1287\/ijoc.2.1.61","volume":"2","author":"J. Gleeson","year":"1990","unstructured":"J. Gleeson and J. Ryan, Identifying minimally infeasible subsystems of inequalities, ORSA Journal on Computing, 2 (1990), pp. 61\u201363.","journal-title":"ORSA Journal on Computing"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/BF02284624","volume":"17","author":"H. J. Greenberg","year":"1996","unstructured":"H. J. Greenberg, Consistency, redundancy, and implied equalities in linear systems, Annals of Mathematics and Artificial Intelligence, 17 (1996), pp. 37\u201383.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR19","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1287\/ijoc.3.3.253","volume":"3","author":"H. J. Greenberg","year":"1991","unstructured":"H. J. Greenberg and F. H. Murphy, Approaches to diagnosing infeasible linear programs, ORSA Journal on Computing, 3 (1991), pp. 253\u2013261.","journal-title":"ORSA Journal on Computing"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"J. H\u00e5astad, Some optimal inapproximability results, in Proc. Twenty-ninth Ann. ACM Symp. Theory of Comp., ACM, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01589098","volume":"45","author":"M. Laurent","year":"1989","unstructured":"M. Laurent, A generalization of antiwebs to independence systems and their canonical facets, Mathematical Programming, 45 (1989), pp. 97\u2013108.","journal-title":"Mathematical Programming"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF01096681","volume":"5","author":"O. L. Mangasarian","year":"1994","unstructured":"O. L. Mangasarian, Misclassification minimization, J. of Global Optimization, 5 (1994), pp. 309\u2013323.","journal-title":"J. of Global Optimization"},{"key":"4_CR23","unstructured":"B. Mishra, Computational real algebraic geometry, in Handbook of Discrete and Computational Geometry, J. Goodman and J. O\u2019Rouke, eds., CRC Press, 1997, ch. 29."},{"key":"4_CR24","unstructured":"N. E. Mn\u00ebv, The universality theorems on the classification problem of configuration varieties and convex polytopes varieties, in Topology and Geometry \u2014 Rohlin Seminar, O. Y. Viro, ed., no. 1346 in Lecture Notes in Mathematics, Springer-Verlag, 1988, pp. 527\u2013543."},{"key":"4_CR25","unstructured":"T. S. Motzkin, Beitr\u00e4ge zur Theorie der Linearen Ungleichungen, PhD thesis, Basel, 1933."},{"key":"4_CR26","unstructured":"M. Parker, A set covering approach to infeasibility analysis of linear programming problems and related issues, PhD thesis, Dep. of Mathematics, University of Colorado at Denver, 1995."},{"key":"4_CR27","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02284626","volume":"17","author":"M. Parker","year":"1996","unstructured":"M. Parker and J. Ryan, Finding the minimum weight IIS cover of an infeasible system of linear inequalities, Annals of Mathematics and Artificial Intelligence, 17 (1996), pp. 107\u2013126.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR28","unstructured":"J. Richter-Gebert, Realization Spaces of Polytopes, no. 1643 in Lecture Notes in Mathematics, Springer-Verlag, 1996."},{"key":"4_CR29","first-page":"17","volume":"81","author":"J. Ryan","year":"1991","unstructured":"J. Ryan, Transversals of IIS-hypergraphs, Congressus Numerantium, 81 (1991), pp. 17\u201322.","journal-title":"Congressus Numerantium"},{"key":"4_CR30","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1137\/S0895480194270469","volume":"9","author":"J. Ryan","year":"1996","unstructured":"\u2014, IIS-hypergraphs, SIAM J. Disc. Math., 9 (1996), pp. 643\u2013653.","journal-title":"SIAM J. Disc. Math."},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"G. M. Ziegler, Lectures on Polytopes, Springer-Verlag, 1994.","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48777-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T16:18:47Z","timestamp":1580314727000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48777-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540660194","9783540487777"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-48777-8_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"30 April 1999","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}