{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T11:12:36Z","timestamp":1772795556594,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,10,27]],"date-time":"2011-10-27T00:00:00Z","timestamp":1319673600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,1]]},"DOI":"10.1007\/s00453-011-9582-6","type":"journal-article","created":{"date-parts":[[2011,10,26]],"date-time":"2011-10-26T17:27:47Z","timestamp":1319650067000},"page":"159-176","source":"Crossref","is-referenced-by-count":20,"title":["Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix"],"prefix":"10.1007","volume":"65","author":[{"given":"Ali","family":"\u00c7ivril","sequence":"first","affiliation":[]},{"given":"Malik","family":"Magdon-Ismail","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,27]]},"reference":[{"issue":"3","key":"9582_CR1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"9582_CR2","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"9582_CR3","doi-asserted-by":"crossref","unstructured":"Boutsidis, C., Drineas, P., Magdon-Ismail, M.: Near-optimal column based matrix reconstruction. (2011). arXiv:1103.0995v1","DOI":"10.1109\/FOCS.2011.21"},{"key":"9582_CR4","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1137\/1.9781611973068.105","volume-title":"SODA\u201909: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"C. Boutsidis","year":"2009","unstructured":"Boutsidis, C., Mahoney, M.W., Drineas, P.: An improved approximation algorithm for the column subset selection problem. In: SODA\u201909: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 968\u2013977 (2009)"},{"key":"9582_CR5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0024-3795(87)90103-0","volume":"88\/89","author":"T.F. Chan","year":"1987","unstructured":"Chan, T.F.: Rank revealing QR factorizations. Linear Algebra Appl. 88\/89, 67\u201382 (1987)","journal-title":"Linear Algebra Appl."},{"key":"9582_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1002\/nla.1680010105","volume":"1","author":"T.F. Chan","year":"1994","unstructured":"Chan, T.F., Hansen, P.: Low-rank revealing QR factorizations. Numer. Linear Algebra Appl. 1, 33\u201344 (1994)","journal-title":"Numer. Linear Algebra Appl."},{"key":"9582_CR7","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1137\/S0895479891223781","volume":"15","author":"S. Chandrasekaran","year":"1994","unstructured":"Chandrasekaran, S., Ipsen, I.C.F.: On rank-revealing factorizations. SIAM J. Matrix Anal. Appl. 15, 592\u2013622 (1994)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"47\u201349","key":"9582_CR8","doi-asserted-by":"crossref","first-page":"4801","DOI":"10.1016\/j.tcs.2009.06.018","volume":"410","author":"A. \u00c7ivril","year":"2009","unstructured":"\u00c7ivril, A., Magdon-Ismail, M.: On selecting a maximum volume sub-matrix of a matrix and related problems. Theor. Comput. Sci. 410(47\u201349), 4801\u20134811 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9582_CR9","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/j.laa.2006.08.034","volume":"422","author":"F.R. Hoog de","year":"2007","unstructured":"de Hoog, F.R., Mattheijb, R.M.M.: Subset selection for matrices. Linear Algebra Appl. 422, 349\u2013359 (2007)","journal-title":"Linear Algebra Appl."},{"key":"9582_CR10","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1109\/FOCS.2010.38","volume-title":"FOCS\u201910: Proceedings of 51st Annual Symposium on Foundations of Computer Science","author":"A. Deshpande","year":"2010","unstructured":"Deshpande, A., Rademacher, L.: Efficient volume sampling for row\/column subset selection. In: FOCS\u201910: Proceedings of 51st Annual Symposium on Foundations of Computer Science, pp. 329\u2013338 (2010)"},{"issue":"1","key":"9582_CR11","doi-asserted-by":"crossref","first-page":"225","DOI":"10.4086\/toc.2006.v002a012","volume":"2","author":"A. Deshpande","year":"2006","unstructured":"Deshpande, A., Rademacher, L., Vempala, S., Wang, G.: Matrix approximation and projective clustering via volume sampling. Theory Comput. 2(1), 225\u2013247 (2006)","journal-title":"Theory Comput."},{"key":"9582_CR12","first-page":"292","volume-title":"RANDOM\u201906: 10th International Workshop on Randomization and Computation","author":"A. Deshpande","year":"2006","unstructured":"Deshpande, A., Vempala, S.: Adaptive sampling and fast low-rank matrix approximation. In: RANDOM\u201906: 10th International Workshop on Randomization and Computation, pp. 292\u2013303 (2006)"},{"issue":"4","key":"9582_CR13","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of lnn for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9582_CR14","doi-asserted-by":"crossref","unstructured":"Golub, G.H., Klema, V., Stewart, G.W.: Rank degeneracy and least squares problems. Technical report, Dept. of Computer Science, Univ. of Maryland, 1976","DOI":"10.3386\/w0165"},{"key":"9582_CR15","volume-title":"Matrix Computations","author":"G.H. Golub","year":"1996","unstructured":"Golub, G.H., Loan, C.V.: Matrix Computations. Johns Hopkins University Press, Baltimore (1996)"},{"key":"9582_CR16","first-page":"47","volume-title":"Contemporary Mathematics","author":"S.A. Goreinov","year":"2001","unstructured":"Goreinov, S.A., Tyrtyshnikov, E.E.: The maximal-volume concept in approximation by low-rank matrices. In: Contemporary Mathematics, vol.\u00a0280, pp. 47\u201351. AMS, Providence (2001)"},{"key":"9582_CR17","doi-asserted-by":"crossref","first-page":"619","DOI":"10.4213\/mzm1644","volume":"62","author":"S.A. Goreinov","year":"1997","unstructured":"Goreinov, S.A., Zamarashkin, N.L., Tyrtyshnikov, E.E.: Pseudo-skeleton approximations by matrices of maximal volume. Mat. Zametki 62, 619\u2013623 (1997)","journal-title":"Mat. Zametki"},{"key":"9582_CR18","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/BF02574058","volume":"13","author":"P. Gritzmann","year":"1995","unstructured":"Gritzmann, P., Klee, V., Larman, D.G.: Largest j-simplices n-polytopes. Discrete Comput. Geom. 13, 477\u2013515 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9582_CR19","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1137\/0917055","volume":"17","author":"M. Gu","year":"1996","unstructured":"Gu, M., Eisenstat, S.C.: Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM J. Sci. Comput. 17(4), 848\u2013869 (1996)","journal-title":"SIAM J. Sci. Comput."},{"key":"9582_CR20","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E. Hazan","year":"2006","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15, 20\u201339 (2006)","journal-title":"Comput. Complex."},{"key":"9582_CR21","first-page":"213","volume":"58","author":"Y.P. Hong","year":"1992","unstructured":"Hong, Y.P., Pan, C.T.: Rank-revealing QR factorizations and the singular value decomposition. Math. Comput. 58, 213\u2013232 (1992)","journal-title":"Math. Comput."},{"key":"9582_CR22","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.ipl.2006.05.006","volume":"100","author":"I. Koutis","year":"2006","unstructured":"Koutis, I.: Parameterized complexity and improved inapproximability for computing the largest j-simplex in a V-polytope. Inf. Process. Lett. 100, 8\u201313 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9582_CR23","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0166-218X(03)00226-9","volume":"134","author":"A. Packer","year":"2004","unstructured":"Packer, A.: Polynomial-time approximation of largest simplices in V-polytopes. Discrete Appl. Math. 134, 213\u2013237 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"9582_CR24","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0024-3795(00)00120-8","volume":"316","author":"C.T. Pan","year":"2000","unstructured":"Pan, C.T.: On the existence and computation of rank-revealing LU factorizations. Linear Algebra Appl. 316(1\u20133), 199\u2013222 (2000)","journal-title":"Linear Algebra Appl."},{"key":"9582_CR25","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1023\/A:1022395308695","volume":"39","author":"C.T. Pan","year":"1999","unstructured":"Pan, C.T., Tang, P.T.P.: Bounds on singular values revealed by QR factorizations. BIT Numer. Math. 39, 740\u2013756 (1999)","journal-title":"BIT Numer. Math."},{"issue":"3","key":"9582_CR26","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R. Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9582-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9582-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9582-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T16:39:39Z","timestamp":1560875979000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9582-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,27]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["9582"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9582-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,27]]}}}