{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T21:02:48Z","timestamp":1762376568247,"version":"3.37.3"},"reference-count":91,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T00:00:00Z","timestamp":1560384000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T00:00:00Z","timestamp":1560384000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2019,11]]},"DOI":"10.1007\/s10589-019-00114-9","type":"journal-article","created":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T10:02:49Z","timestamp":1560420169000},"page":"387-441","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Computing the spark: mixed-integer programming for the (vector) matroid girth problem"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7744-836X","authenticated-orcid":false,"given":"Andreas M.","family":"Tillmann","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,13]]},"reference":[{"issue":"6","key":"114_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1007\/s00041-012-9235-4","volume":"18","author":"B Alexeev","year":"2012","unstructured":"Alexeev, B., Cahill, J., Mixon, D.G.: Full spark frames. J. Fourier Anal. Appl. 18(6), 1167\u20131194 (2012)","journal-title":"J. Fourier Anal. Appl."},{"key":"114_CR2","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","volume":"147","author":"E Amaldi","year":"1995","unstructured":"Amaldi, E., Kann, V.: The complexity and approximability of finding maximum feasible subsystems of linear relations. Theor. Comput. Sci. 147, 181\u2013210 (1995)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"114_CR3","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0304-3975(97)00115-1","volume":"209","author":"E Amaldi","year":"1998","unstructured":"Amaldi, E., Kann, V.: On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theor. Comput. Sci. 209(1\u20132), 237\u2013260 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"114_CR4","unstructured":"Arellano, J.D.: Algorithms to find the girth and cogirth of a linear matroid. Ph.D. thesis, Rice University (2014)"},{"issue":"1","key":"114_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1109\/TASE.2013.2271703","volume":"11","author":"JD Arellano","year":"2014","unstructured":"Arellano, J.D., Hicks, I.V.: Degree of redundancy of linear systems using implicit set covering. IEEE Trans. Autom. Sci. Eng. 11(1), 274\u2013279 (2014)","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"issue":"2","key":"114_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54(2), 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"114_CR7","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.orl.2008.09.009","volume":"37","author":"P Aveila","year":"2009","unstructured":"Aveila, P., Boccia, M., Vasilyev, I.: Computational experience with general cutting planes for the set covering problem. Oper. Res. Lett. 37(1), 16\u201320 (2009)","journal-title":"Oper. Res. Lett."},{"issue":"6","key":"114_CR8","doi-asserted-by":"publisher","first-page":"1860","DOI":"10.1137\/S1064827502401953","volume":"25","author":"C Aykanat","year":"2004","unstructured":"Aykanat, C., Pinar, A., \u00c7ataly\u00fcrek, U.: Permuting sparse rectangular matrices into block-diagonal form. SIAM J. Sci. Comput. 25(6), 1860\u20131879 (2004)","journal-title":"SIAM J. Sci. Comput."},{"key":"114_CR9","first-page":"19","volume":"12","author":"E Balas","year":"1980","unstructured":"Balas, E.: Cutting planes from conditional bounds: a new approach to set covering. Math. Prog. 12, 19\u201336 (1980)","journal-title":"Math. Prog."},{"key":"114_CR10","first-page":"37","volume":"12","author":"E Balas","year":"1980","unstructured":"Balas, E., Ho, A.: Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. Math. Prog. 12, 37\u201360 (1980)","journal-title":"Math. Prog."},{"issue":"1","key":"114_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/0123007","volume":"23","author":"E Balas","year":"1972","unstructured":"Balas, E., Jeroslow, R.: Canonical cuts on the unit hypercube. SIAM J. Appl. Math. 23(1), 61\u201369 (1972)","journal-title":"SIAM J. Appl. Math."},{"issue":"1\u20133","key":"114_CR12","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01582278","volume":"43","author":"E Balas","year":"1989","unstructured":"Balas, E., Ng, S.M.: On the set covering polytope: I. All the facets with coefficients in 0, 1, 2. Math. Program. 43(1\u20133), 57\u201369 (1989)","journal-title":"Math. Program."},{"issue":"4","key":"114_CR13","doi-asserted-by":"publisher","first-page":"1151","DOI":"10.1109\/TASE.2013.2259479","volume":"10","author":"M Bausal","year":"2013","unstructured":"Bausal, M., Kianfar, K., Ding, Y., Moreno-Centeno, E.: Hybridization of bound-and-decompose and mixed integer feasibility checking to measure redundancy in structured linear systems. IEEE Trans. Autom. Sci. Eng. 10(4), 1151\u20131157 (2013)","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"issue":"2","key":"114_CR14","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0377-2217(92)90215-U","volume":"58","author":"JE Beasley","year":"1992","unstructured":"Beasley, J.E., Jornsten, K.: Enhancing an algorithm for set covering problems. Eur. J. Oper. Res. 58(2), 293\u2013300 (1992)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"114_CR15","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/BF01389453","volume":"47","author":"MW Berry","year":"1985","unstructured":"Berry, M.W., Heath, M.T., Kaneka, I., Lawo, M., Plemmons, R.J., Ward, R.C.: An algorithm to compute a sparse basis of the null space. Numer. Math. 47(4), 483\u2013504 (1985)","journal-title":"Numer. Math."},{"issue":"4","key":"114_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0167-6377(94)90074-4","volume":"15","author":"RE Bixby","year":"1994","unstructured":"Bixby, R.E., Saltzman, M.J.: Recovering an optimal LP basis from an interior point solution. Oper. Res. Lett. 15(4), 169\u2013178 (1994)","journal-title":"Oper. Res. Lett."},{"key":"114_CR17","unstructured":"Bornd\u00f6rfer, R.: Aspects of set packing, partitioning, and covering. Doctoral dissertation. TU Berlin, Germany (1998)"},{"key":"114_CR18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511803888","volume-title":"Combinatorics: topics, techniques. Algorithms","author":"PJ Cameron","year":"1994","unstructured":"Cameron, P.J.: Combinatorics: topics, techniques. Algorithms. Cambridge University Press, Cambridge (1994)"},{"issue":"12","key":"114_CR19","doi-asserted-by":"publisher","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"E Cand\u00e8s","year":"2005","unstructured":"Cand\u00e8s, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inform. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"114_CR20","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1023\/A:1019225027893","volume":"98","author":"A Caprara","year":"2000","unstructured":"Caprara, A., Toth, P., Fischetti, M.: Algorithms for the set covering problem. Ann. Oper. Res. 98, 353\u2013371 (2000)","journal-title":"Ann. Oper. Res."},{"issue":"1\u20133","key":"114_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01580890","volume":"56","author":"SF Chang","year":"1992","unstructured":"Chang, S.F., McCormick, S.T.: A hierarchical algorithm for making sparse matrices sparser. Math. Program. 56(1\u20133), 1\u201330 (1992)","journal-title":"Math. Program."},{"issue":"1","key":"114_CR22","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/S1064827596304010","volume":"20","author":"SS Chen","year":"1998","unstructured":"Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33\u201361 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"4","key":"114_CR23","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s10208-002-0076-4","volume":"3","author":"A Chistov","year":"2003","unstructured":"Chistov, A., Fournier, H., Gurvits, L., Koiran, P.: Vandermonde matrices, NP-completeness, and transversal subspaces. Found. Comput. Math. 3(4), 421\u2013427 (2003)","journal-title":"Found. Comput. Math."},{"issue":"18","key":"114_CR24","doi-asserted-by":"publisher","first-page":"2456","DOI":"10.1016\/j.dam.2007.06.015","volume":"155","author":"JJ Cho","year":"2007","unstructured":"Cho, J.J., Chen, Y., Ding, Y.: On the (co)girth of a connected matroid. Discrete Appl. Math. 155(18), 2456\u20132470 (2007)","journal-title":"Discrete Appl. Math."},{"key":"114_CR25","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1186\/s13634-018-0535-y","volume":"2018","author":"M Cho","year":"2018","unstructured":"Cho, M., Mishra, K.V., Xu, W.: Computable performance guarantees for compressed sensing matrices. EURASIP J. Adv. Signal Process. 2018, 16 (2018)","journal-title":"EURASIP J. Adv. Signal Process."},{"key":"114_CR26","unstructured":"Coleman, T.F., Pothen, A.: The sparse null space basis problem. Technical Report TR 84-598, Cornell University, Ithaca, NY, USA (1984)"},{"key":"114_CR27","doi-asserted-by":"crossref","unstructured":"Damaschke, P., E\u011fecio\u011flu, O., Molokov, L.: Fixed-Parameter Tractability of Error Correction in Graphical Linear Systems. In: Ghosh, S.K., Tokuyama, T. (eds.) Proceedings of the WALCOM. 2013, LNCS, vol. 7748, pp. 245\u2013256. Springer (2013)","DOI":"10.1007\/978-3-642-36065-7_23"},{"key":"114_CR28","first-page":"1269","volume":"9","author":"A d\u2019Aspremont","year":"2008","unstructured":"d\u2019Aspremont, A., Bach, F., Ghaoui, L.E.: Optimal solutions for sparse principal component analysis. J. Mach. Learn. Res. 9, 1269\u20131294 (2008)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"114_CR29","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s10107-010-0416-0","volume":"127","author":"A d\u2019Aspremont","year":"2011","unstructured":"d\u2019Aspremont, A., Ghaoui, L.E.: Testing the nullspace property using semidefinite programming. Math. Program. 127(1), 123\u2013144 (2011)","journal-title":"Math. Program."},{"issue":"3","key":"114_CR30","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1137\/050645506","volume":"49","author":"A d\u2019Aspremont","year":"2007","unstructured":"d\u2019Aspremont, A., Ghaoui, L.E., Jordan, M.I., Lanckriet, G.R.G.: A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49(3), 434\u2013448 (2007)","journal-title":"SIAM Rev."},{"issue":"4\u20136","key":"114_CR31","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1016\/j.jco.2007.04.002","volume":"23","author":"RA DeVore","year":"2007","unstructured":"DeVore, R.A.: Deterministic constructions of compressed sensing matrices. J. Complex. 23(4\u20136), 918\u2013925 (2007)","journal-title":"J. Complex."},{"issue":"5","key":"114_CR32","doi-asserted-by":"publisher","first-page":"3093","DOI":"10.1109\/TIT.2011.2181819","volume":"58","author":"AG Dimakis","year":"2012","unstructured":"Dimakis, A.G., Smarandache, R., Vontobel, P.O.: LDPC codes for compressed sensing. IEEE Trans. Inf. Theory 58(5), 3093\u20133114 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"114_CR33","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"114_CR34","doi-asserted-by":"publisher","first-page":"2197","DOI":"10.1073\/pnas.0437847100","volume":"100","author":"DL Donoho","year":"2003","unstructured":"Donoho, D.L., Elad, M.: Optimally sparse representation in general (non-orthogonal) dictionaries via $$\\ell ^1$$ minimization. Proc. Natl. Acad. Sci. USA 100(5), 2197\u20132202 (2003)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"2","key":"114_CR35","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1006\/jsco.1998.0204","volume":"26","author":"S Egner","year":"1998","unstructured":"Egner, S., Minkwitz, T.: Sparsification of rectangular matrices. J. Symb. Comput. 26(2), 135\u2013149 (1998)","journal-title":"J. Symb. Comput."},{"key":"114_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7011-4","volume-title":"Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing","author":"M Elad","year":"2010","unstructured":"Elad, M.: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer, Heidelberg (2010)"},{"key":"114_CR37","first-page":"2","volume":"66","author":"MC Ferris","year":"2001","unstructured":"Ferris, M.C., Pataki, G., Schmieta, S.: Solving the seymour problem. Optima 66, 2\u20136 (2001)","journal-title":"Optima"},{"key":"114_CR38","unstructured":"Fischer, T.: Konstruktion von d\u00fcnn besetzten Sensing-Matrizen. Diploma Thesis, TU Darmstadt, Germany (2012) (in German)"},{"key":"114_CR39","volume-title":"A Mathematical Introduction to Compressive Sensing. Applied and Numeric Harmonic Analysis","author":"S Foucart","year":"2013","unstructured":"Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Applied and Numeric Harmonic Analysis. Birkh\u00e4user, Basel (2013)"},{"key":"114_CR40","unstructured":"Gally, T., Pfetsch, M.E.: Computing Restricted Isometry Constants via Mixed-Integer Semidefinite Programming. Optimization Online E-print (2016). \n                    http:\/\/www.optimization-online.org\/DB_HTML\/2016\/04\/5395.html\n                    \n                  . Accessed 20 Apr 2018"},{"key":"114_CR41","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"5","key":"114_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5121\/ijdps.2012.3501","volume":"3","author":"W Gharibi","year":"2012","unstructured":"Gharibi, W.: An improved lower bound of the spark with application. Int. J. Distrib. Parallel Syst. 3(5), 1\u20138 (2012)","journal-title":"Int. J. Distrib. Parallel Syst."},{"issue":"3","key":"114_CR43","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1137\/0608037","volume":"8","author":"JR Gilbert","year":"1987","unstructured":"Gilbert, J.R., Heath, M.T.: Computing a sparse basis for the null space. SIAM J. Algebraic Discrete Methods 8(3), 446\u2013459 (1987)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"2","key":"114_CR44","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/s00453-015-0042-6","volume":"76","author":"LA Gottlieb","year":"2016","unstructured":"Gottlieb, L.A., Neylon, T.: Matrix sparsification and the sparse null space problem. Algorithmica 76(2), 426\u2013444 (2016)","journal-title":"Algorithmica"},{"issue":"2","key":"114_CR45","doi-asserted-by":"publisher","first-page":"3320","DOI":"10.1109\/TIT.2003.820031","volume":"49","author":"R Gribonval","year":"2003","unstructured":"Gribonval, R., Nielsen, M.: Sparse representations in unions of bases. IEEE Trans. Inf. Theory 49(2), 3320\u20133325 (2003)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"114_CR46","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0024-3795(94)90407-3","volume":"212\u2013213","author":"JW Grossman","year":"1994","unstructured":"Grossman, J.W., Kulkarni, D.M., Schochetman, I.E.: Algebraic graph theory without orientation. Linear Algebra Appl. 212\u2013213, 289\u2013307 (1994)","journal-title":"Linear Algebra Appl."},{"key":"114_CR47","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0024-3795(93)00173-W","volume":"218","author":"JW Grossman","year":"1995","unstructured":"Grossman, J.W., Kulkarni, D.M., Schochetman, I.E.: On the minors of an incidence matrix and its Smith normal form. Linear Algebra Appl. 218, 213\u2013224 (1995)","journal-title":"Linear Algebra Appl."},{"key":"114_CR48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics,","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, 2nd edn. Springer, Berlin (1993)","edition":"2"},{"issue":"7","key":"114_CR49","doi-asserted-by":"publisher","first-page":"4753","DOI":"10.1109\/TIT.2012.2191697","volume":"58","author":"M Helmling","year":"2012","unstructured":"Helmling, M., Ruzika, S., Tanatmis, A.: Mathematical programming decoding of binary linear codes: theory and algorithms. IEEE Trans. Inf. Theory 58(7), 4753\u20134769 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"114_CR50","unstructured":"Helmling, M., Scholl, S., Gensheimer, F., Dietz, T., Kraft, K., Ruzika, S., Wehn, N.: Database of channel codes and ML simulation results (2017). \n                    https:\/\/www.uni-kl.de\/channel-codes\/channelcodes\n                    \n                  . Accessed 20 Apr 2018"},{"key":"114_CR51","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/B978-0-12-566780-7.50017-9","volume-title":"Progress in Combinatorial Optimization","author":"AJ Hoffman","year":"1984","unstructured":"Hoffman, A.J., McCormick, S.T.: A fast algorithm that makes matrices optimally sparse. In: Pulleyblank, W.R. (ed.) Progress in Combinatorial Optimization, pp. 185\u2013196. Academic Press, Amsterdam (1984)"},{"issue":"4","key":"114_CR52","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"key":"114_CR53","first-page":"870","volume":"2009","author":"MA Iwen","year":"2009","unstructured":"Iwen, M.A.: Simple deterministically constructible RIP matrices with sublinear Fourier sampling requirements. Proc. CISS 2009, 870\u2013875 (2009)","journal-title":"Proc. CISS"},{"issue":"1","key":"114_CR54","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/0211014","volume":"11","author":"PM Jensen","year":"1982","unstructured":"Jensen, P.M., Korte, B.: Complexity of matroid property algorithms. SIAM J. Comput. 11(1), 184\u2013190 (1982)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"114_CR55","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1137\/070686676","volume":"31","author":"S Jokar","year":"2008","unstructured":"Jokar, S., Pfetsch, M.E.: Exact and approximate sparse solutions of underdetermined linear equations. SIAM J. Sci. Comput. 31(1), 23\u201344 (2008)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"114_CR56","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10107-010-0417-z","volume":"127","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A.: On verifiable sufficient conditions for sparse signal recovery via $$\\ell 1$$ minimization. Math. Program. 127(1), 57\u201388 (2011)","journal-title":"Math. Program."},{"issue":"4","key":"114_CR57","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1109\/TCOMM.2010.04.090164","volume":"58","author":"AB Keha","year":"2010","unstructured":"Keha, A.B., Duman, T.: Minimum distance computation of LDPC codes using a branch and cut algorithm. IEEE Trans. Commun. 58(4), 1072\u20131079 (2010)","journal-title":"IEEE Trans. Commun."},{"issue":"4","key":"114_CR58","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1137\/S0895480103428338","volume":"19","author":"L Khachiyan","year":"2006","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: On the complexity of some enumeration problems for matroids. SIAM J. Discrete Math. 19(4), 966\u2013984 (2006)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"114_CR59","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1109\/TASE.2010.2089449","volume":"8","author":"K Kianfar","year":"2011","unstructured":"Kianfar, K., Pourhabib, A., Ding, Y.: An integer programming approach for analyzing the measurement redundancy in structured linear systems. IEEE Trans. Autom. Sci. Eng. 8(2), 447\u2013450 (2011)","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"114_CR60","doi-asserted-by":"crossref","unstructured":"King, E.: Algebraic and geometric spread in finite frames. In: Proceedings of the SPIE 9597, Wavelets and Sparsity XVI, Article no. 95970B (2015)","DOI":"10.1117\/12.2188541"},{"key":"114_CR61","unstructured":"Koiran, P., Zouzias, A.: On the Certification of the Restricted Isometry Property. \n                    arXiv:1103.4984\n                    \n                   [cs.CC] (2011). Accessed 20 Apr 2018"},{"issue":"3","key":"114_CR62","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1137\/07070111X","volume":"51","author":"TG Kolda","year":"2009","unstructured":"Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455\u2013500 (2009)","journal-title":"SIAM Rev."},{"issue":"2","key":"114_CR63","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0024-3795(77)90069-6","volume":"18","author":"JB Kruskal","year":"1977","unstructured":"Kruskal, J.B.: Three-way arrays: rank and uniqueness of trilinear decompositions. Linear Algebra Appl. 18(2), 95\u2013138 (1977)","journal-title":"Linear Algebra Appl."},{"key":"114_CR64","unstructured":"Lange, J.H., Pfetsch, M.E., Seib, B.M., Tillmann, A.M.: Sparse Recovery with Integrality Constraints. \n                    arXiv:1608.08678\n                    \n                   [cs.IT] (2016). Accessed 20 Apr 2018"},{"issue":"1","key":"114_CR65","doi-asserted-by":"publisher","first-page":"195","DOI":"10.3934\/amc.2016.10.195","volume":"10","author":"P Lison\u011bk","year":"2016","unstructured":"Lison\u011bk, P., Trummer, L.: Algorithms for the minimum weight of linear codes. Adv. Math. Commun. 10(1), 195\u2013207 (2016)","journal-title":"Adv. Math. Commun."},{"key":"114_CR66","first-page":"479","volume":"2013","author":"XJ Liu","year":"2013","unstructured":"Liu, X.J., Xia, S.T.: Constructions of quasi-cyclic measurement matrices based on array codes. Proc. ISIT 2013, 479\u2013483 (2013)","journal-title":"Proc. ISIT"},{"key":"114_CR67","unstructured":"Maculan, N., Macambira, E.M., de\u00a0Souza, C.C.: Geometrical Cuts for 0\u20131 Integer Programming. Technical Report IC-02-006, Instituto de Computacao, Universidade Estadual de Campinas (2002)"},{"key":"114_CR68","unstructured":"Maher, S.J., Fischer, T., Gally, T., Gamrath, G., Gleixner, A., Gottwald, R.L., Hendel, G., Koch, T., L\u00fcbbecke, M.E., Miltenberger, M., M\u00fcller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Weninger, D., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 4.0. Technical Report 17-12, ZIB (2017)"},{"issue":"8","key":"114_CR69","doi-asserted-by":"publisher","first-page":"2166","DOI":"10.1109\/78.705428","volume":"46","author":"A Manikas","year":"1998","unstructured":"Manikas, A., Proukakis, C.: Modeling and estimation of ambiguities in linear arrays. IEEE Trans. Signal Process. 46(8), 2166\u20132179 (1998)","journal-title":"IEEE Trans. Signal Process."},{"key":"114_CR70","doi-asserted-by":"crossref","unstructured":"McCormick, S.T.: A Combinatorial Approach to Some Sparse Matrix Problems. Ph.D. thesis, Stanford University (1983)","DOI":"10.21236\/ADA131387"},{"issue":"1\u20133","key":"114_CR71","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF01588780","volume":"49","author":"ST McCormick","year":"1990","unstructured":"McCormick, S.T.: Making sparse matrices sparser: computational results. Math. Program. 49(1\u20133), 91\u2013111 (1990)","journal-title":"Math. Program."},{"issue":"3","key":"114_CR72","doi-asserted-by":"publisher","first-page":"337","DOI":"10.6028\/jres.080B.034","volume":"80B","author":"E Minieka","year":"1976","unstructured":"Minieka, E.: Finding the circuits of a matroid. J. Res. Natl. Bur. Stand. B 80B(3), 337\u2013342 (1976)","journal-title":"J. Res. Natl. Bur. Stand. B"},{"key":"114_CR73","first-page":"65","volume-title":"Handbook of Applied Optimization","author":"JE Mitchell","year":"2002","unstructured":"Mitchell, J.E.: Branch-and-cut algorithms for combinatorial optimization problems. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimization, pp. 65\u201377. Oxford Univ. Press, Oxford (2002)"},{"issue":"4","key":"114_CR74","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/BF02251238","volume":"31","author":"B Monien","year":"1983","unstructured":"Monien, B.: The complexity of determining a shortest cycle of even length. Computing 31(4), 355\u2013369 (1983)","journal-title":"Computing"},{"issue":"14","key":"114_CR75","doi-asserted-by":"publisher","first-page":"3566","DOI":"10.1109\/TSP.2016.2550020","volume":"64","author":"RR Naidu","year":"2016","unstructured":"Naidu, R.R., Jampana, P., Sastry, C.S.: Deterministic compressed sensing matrices: construction via Euler squares and applications. IEEE Trans. Signal Process. 64(14), 3566\u20133575 (2016)","journal-title":"IEEE Trans. Signal Process."},{"key":"114_CR76","volume-title":"Matroid Theory. Oxford Graduate Texts Mathematics","author":"JG Oxley","year":"2011","unstructured":"Oxley, J.G.: Matroid Theory. Oxford Graduate Texts Mathematics, 2nd edn. Oxford Univ. Press, Oxford (2011)","edition":"2"},{"issue":"29","key":"114_CR77","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1017\/S0305004100056498","volume":"87","author":"GC Robinson","year":"1980","unstructured":"Robinson, G.C., Welsh, D.J.A.: The computational complexity of matroid properties. Math. Proc. Camb. Philos. Soc. 87(29), 29\u201345 (1980)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"114_CR78","volume-title":"Combinatorial optimization: polyhedra and efficiency, volume A algorithms and combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, volume A algorithms and combinatorics, vol. 24. Springer, Berlin (2003)"},{"key":"114_CR79","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0095-8956(80)90075-1","volume":"28","author":"PD Seymour","year":"1980","unstructured":"Seymour, P.D.: Decomposition of regular matroids. J. Combin. Theory Ser. B 28, 305\u2013359 (1980)","journal-title":"J. Combin. Theory Ser. B"},{"key":"114_CR80","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1006\/jctb.1994.1033","volume":"61","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D.: A note on hyperplane generation. J. Combin. Theory Ser. B 61, 88\u201391 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"114_CR81","first-page":"2216","volume":"2009","author":"A Tanatmis","year":"2009","unstructured":"Tanatmis, A., Ruzika, S., Hamacher, H.W., Punekar, M., Kienle, F., Wehn, N.: Valid inequalities for binary linear codes. Proc. ISIT 2009, 2216\u20132220 (2009)","journal-title":"Proc. ISIT"},{"key":"114_CR82","unstructured":"Tillmann, A.M.: Computational Aspects of Compressed Sensing. Doctoral dissertation. TU Darmstadt, Germany (2013)"},{"issue":"1","key":"114_CR83","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1109\/LSP.2014.2345761","volume":"22","author":"AM Tillmann","year":"2015","unstructured":"Tillmann, A.M.: On the computational intractability of exact and approximate dictionary learning. IEEE Signal Process. Lett. 22(1), 45\u201349 (2015)","journal-title":"IEEE Signal Process. Lett."},{"key":"114_CR84","first-page":"7148","volume":"2014","author":"AM Tillmann","year":"2014","unstructured":"Tillmann, A.M., Gribonval, R., Pfetsch, M.E.: Projection onto the cosparse set is NP-hard. Proc. ICASSP 2014, 7148\u20137152 (2014)","journal-title":"Proc. ICASSP"},{"issue":"2","key":"114_CR85","doi-asserted-by":"publisher","first-page":"1248","DOI":"10.1109\/TIT.2013.2290112","volume":"60","author":"AM Tillmann","year":"2014","unstructured":"Tillmann, A.M., Pfetsch, M.E.: The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Trans. Inf. Theory 60(2), 1248\u20131259 (2014)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"114_CR86","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0095-8956(90)90030-4","volume":"49","author":"K Truemper","year":"1990","unstructured":"Truemper, K.: A decomposition theory for matroids. V. Testing of matrix total unimodularity. J. Combin. Theory Ser. B 49, 241\u2013281 (1990)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"6","key":"114_CR87","doi-asserted-by":"publisher","first-page":"1757","DOI":"10.1109\/18.641542","volume":"43","author":"A Vardy","year":"1997","unstructured":"Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory 43(6), 1757\u20131766 (1997)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"114_CR88","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s12532-012-0048-x","volume":"5","author":"M Walter","year":"2013","unstructured":"Walter, M., Truemper, K.: Implementation of a unimodularity test. Math. Program. Comput. 5(1), 57\u201373 (2013)","journal-title":"Math. Program. Comput."},{"issue":"11","key":"114_CR89","doi-asserted-by":"publisher","first-page":"1960","DOI":"10.1109\/LSP.2015.2447934","volume":"22","author":"J Zhang","year":"2015","unstructured":"Zhang, J., Han, G., Fang, Y.: Deterministic construction of compressed sensing matrices from protograph LDPC codes. IEEE Signal Process. Lett. 22(11), 1960\u20131964 (2015)","journal-title":"IEEE Signal Process. Lett."},{"key":"114_CR90","doi-asserted-by":"publisher","DOI":"10.1017\/9781108277587","volume-title":"Matrix Analysis and Applications","author":"XD Zhang","year":"2017","unstructured":"Zhang, X.D.: Matrix Analysis and Applications. Cambridge Univ. Press, Cambridge (2017)"},{"key":"114_CR91","doi-asserted-by":"crossref","unstructured":"Zhu, Z., So, A.M.C., Ye, Y.: Fast and near-optimal matrix completion via randomized basis pursuit. In: Ji, L., Poon, Y.S., Yang, L., Yau, S.T. (eds.) Proceedings of the 5th ICCM. AMS\/IP Studies in Advanced Mathematics, vol. 51, pp. 859\u2013882. AMS and International Press (2012)","DOI":"10.1090\/amsip\/051.2\/22"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-019-00114-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-019-00114-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-019-00114-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,11]],"date-time":"2020-06-11T23:16:08Z","timestamp":1591917368000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-019-00114-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,13]]},"references-count":91,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["114"],"URL":"https:\/\/doi.org\/10.1007\/s10589-019-00114-9","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2019,6,13]]},"assertion":[{"value":"21 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}