{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:01:34Z","timestamp":1725663694663},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_168","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:29Z","timestamp":1330262429000},"page":"521-532","source":"Crossref","is-referenced-by-count":7,"title":["On the approximability of finding maximum feasible subsystems of linear systems"],"prefix":"10.1007","author":[{"given":"Edoardo","family":"Amaldi","sequence":"first","affiliation":[]},{"given":"Viggo","family":"Kann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"42_CR1","first-page":"55","volume-title":"Artificial Neural Networks","author":"E. Amaldi","year":"1991","unstructured":"E. Amaldi. On the complexity of training perceptions. In T. Kohonen et al., editor, Artificial Neural Networks, pages 55\u201360, Amsterdam, 1991. Elsevier science publishing company."},{"key":"42_CR2","unstructured":"E. Amaldi and V. Kann, 1993. Manuscript in preparation."},{"volume-title":"Technical Report ORWP-11-93, Department of Mathematics, Swiss Federal Institute of Technology, Lausanne and Technical Report TRITA-NA-9313","year":"1993","author":"E. Amaldi","key":"42_CR3","unstructured":"E. Amaldi and V. Kann. The complexity and approximability of finding maximum feasible subsystems of linear relations. Technical Report ORWP-11-93, Department of Mathematics, Swiss Federal Institute of Technology, Lausanne and Technical Report TRITA-NA-9313, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1993."},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equation. In Proc. of 34rd Ann. IEEE Symp. on Foundations of Comput. Sci., pages 724\u2013733, 1993.","DOI":"10.1109\/SFCS.1993.366815"},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. of 33rd Ann. IEEE Symp. on Foundations of Comput. Sci., pages 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"42_CR6","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman and G. Schnitger. On the complexity of approximating the independent set problem. Inform. and Comput., 96:77\u201394, 1992.","journal-title":"Inform. and Comput."},{"volume-title":"Computers and Intractability: a guide to the theory of NP-completeness","year":"1979","author":"M. R. Garey","key":"42_CR7","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco, 1979."},{"volume-title":"volume 22 of Annals of Discrete Mathematics","year":"1984","author":"R. Greer","key":"42_CR8","unstructured":"R. Greer. Trees and Hills: Methodology for Maximizing Functions of Systems of Linear Relations, volume 22 of Annals of Discrete Mathematics. Elsevier science publishing company, Amsterdam, 1984."},{"key":"42_CR9","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0020-0190(93)90076-L","volume":"47","author":"J. H\u00e5stad","year":"1993","unstructured":"J. H\u00e5stad, S. Phillips, and S. Safra. A well-characterized approximation problem. Inform. Process. Lett., 47:301\u2013305, 1993.","journal-title":"Inform. Process. Lett."},{"volume-title":"Technical Report CS-92-9","year":"1992","author":"K-U. H\u00f6ffgen","key":"42_CR10","unstructured":"K-U. H\u00f6ffgen, H-U. Simon, and K. van Horn. Robust trainability of single neurons. Technical Report CS-92-9, Computer Science Department, Brigham Young University, Provo, 1992."},{"key":"42_CR11","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","volume":"6","author":"D. S. Johnson","year":"1978","unstructured":"D. S. Johnson and F. P. Preparata. The densest hemisphere problem. Theoretical Computer Science, 6:93\u2013107, 1978.","journal-title":"Theoretical Computer Science"},{"volume-title":"PhD thesis","year":"1992","author":"V. Kann","key":"42_CR12","unstructured":"V. Kann. On the Approximability of NP-complete Optimization Problems. PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992."},{"key":"42_CR13","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"N. Karmarkar. A new polynomial time algorithm for linear programming. Combinatorica, 4:373\u2013395, 1984.","journal-title":"Combinatorica"},{"key":"42_CR14","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. In Proc. Twenty fifth Ann. ACM Symp. on Theory of Comp., pages 286\u2013293, 1993.","DOI":"10.1145\/167088.167172"},{"key":"42_CR15","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. J. Comput. System Sci., 43:425\u2013440, 1991.","journal-title":"J. Comput. System Sci."},{"key":"42_CR16","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1109\/T-C.1973.223652","volume":"22","author":"R. E. Warmack","year":"1973","unstructured":"R. E. Warmack and R. C. Gonzalez. An algorithm for optimal solution of linear inequalities and its application to pattern recognition. IEEE Trans. on Computers, 22:1065\u20131075, 1973.","journal-title":"IEEE Trans. on Computers"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_168.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:08:05Z","timestamp":1619572085000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_168"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_168","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}