{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:13Z","timestamp":1750219813352,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,10,14]],"date-time":"2023-10-14T00:00:00Z","timestamp":1697241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            One way to solve very large linear programs in standard form is to apply a random projection to the constraints, then solve the projected linear program [\n            <jats:xref ref-type=\"bibr\">63<\/jats:xref>\n            ]. This will yield a guaranteed bound on the optimal value, as well as a solution to the projected linear program. The process of constructing an approximate solution of the original linear program is called solution retrieval. We improve theoretical bounds on the approximation error of the retrieved solution obtained as in Reference [\n            <jats:xref ref-type=\"bibr\">42<\/jats:xref>\n            ] and propose an improved retrieval method based on alternating projections. We show empirical results illustrating the practical benefits of the new approach.\n          <\/jats:p>","DOI":"10.1145\/3617506","type":"journal-article","created":{"date-parts":[[2023,8,28]],"date-time":"2023-08-28T11:45:04Z","timestamp":1693223104000},"page":"1-33","source":"Crossref","is-referenced-by-count":0,"title":["Random Projections for Linear Programming: An Improved Retrieval Phase"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3139-6821","authenticated-orcid":false,"given":"Leo","family":"Liberti","sequence":"first","affiliation":[{"name":"LIX CNRS, \u00c9cole Polytechnique, Institut Polytechnique de Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0209-0655","authenticated-orcid":false,"given":"Benedetto","family":"Manca","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Informatica, Universit\u00e0 di Cagliari, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3783-3036","authenticated-orcid":false,"given":"Pierre-Louis","family":"Poirion","sequence":"additional","affiliation":[{"name":"RIKEN Center for Advanced Intelligence Project, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,10,14]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00025-4"},{"key":"e_1_3_1_3_2","series-title":"Operations Research & Management Science","volume-title":"Handbook on Semidefinite, Conic, and Polynomial Optimization","author":"Alizadeh F.","year":"2012","unstructured":"F. Alizadeh. 2012. An introduction to formally real Jordan Algebras and their applications in optimization. In Handbook on Semidefinite, Conic, and Polynomial Optimization, M. Anjos and J. Lasserre (Eds.). Operations Research & Management Science, Vol. 166. Springer, Boston, MA."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iau005"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s10589-017-9942-5","article-title":"A new projection method for finding the closest point in the intersection of convex sets","volume":"69","author":"Artacho F. Arag\u00f3n","year":"2018","unstructured":"F. Arag\u00f3n Artacho and R. Campoy. 2018. A new projection method for finding the closest point in the intersection of convex sets. Comput. Optimiz. Appl. 69 (2018), 99\u2013132.","journal-title":"Comput. Optimiz. Appl."},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF02614310","article-title":"Measure concentration in optimization","volume":"79","author":"Barvinok A.","year":"1997","unstructured":"A. Barvinok. 1997. Measure concentration in optimization. Math. Program. 79 (1997), 33\u201353.","journal-title":"Math. Program."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.3.267"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2018.11.012"},{"key":"e_1_3_1_9_2","first-page":"298","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Boutsidis C.","year":"2010","unstructured":"C. Boutsidis, A. Zouzias, and P. Drineas. 2010. Random projections for k-means clustering. In Advances in Neural Information Processing Systems (NIPS). NIPS Foundation, La Jolla, CA, 298\u2013306."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"e_1_3_1_11_2","article-title":"Global optimization using random embeddings","author":"Cartis C.","year":"2023","unstructured":"C. Cartis, E. Massart, and A. Otemissov. 2023. Global optimization using random embeddings. Math. Programm. B 200 (2023), 781\u2013829.","journal-title":"Math. Programm. B"},{"key":"e_1_3_1_12_2","first-page":"1","article-title":"Faster randomized interior point methods for tall\/wide linear programs","volume":"23","author":"Chowdhury A.","year":"2022","unstructured":"A. Chowdhury, G. Dexter, P. London, H. Avron, and P. Drineas. 2022. Faster randomized interior point methods for tall\/wide linear programs. J. Mach. Learn. Res. 23 (2022), 1\u201348.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_1_13_2","volume-title":"Proceedings of the 24th Symposium on Discrete Algorithms","author":"Clarskon L.","year":"2013","unstructured":"L. Clarskon, P. Drineas, M. Magdon-Ismail, M. Mahoney, X. Meng, and D. Woodruff. 2013. The fast Cauchy transform and faster robust linear regression. In Proceedings of the 24th Symposium on Discrete Algorithms. ACM, New York, NY."},{"key":"e_1_3_1_14_2","first-page":"11:1\u201311:14","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs)","volume":"55","author":"Cohen M. B.","year":"2016","unstructured":"M. B. Cohen, J. Nelson, and D. P. Woodruff. 2016. Optimal approximate matrix product in terms of stable rank. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (LIPIcs), I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, and D. Sangiorgi (Eds.), Vol. 55. Dagstuhl Publishing, Saarbr\u00fccken, 11:1\u201311:14."},{"key":"e_1_3_1_15_2","series-title":"Optimization and Its Applications","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/978-1-4419-9569-8_10","volume-title":"Fixed-point Algorithms for Inverse Problems in Science and Engineering","author":"Combettes P.","year":"2011","unstructured":"P. Combettes and J.-C. Pesquet. 2011. Proximal splitting methods in signal processing. In Fixed-point Algorithms for Inverse Problems in Science and Engineering, H. Bauschke, R. Burachik, P. Combettes, V. Elser, D. Russel Luke, and H. Wolkowicz (Eds.). Optimization and Its Applications, Vol. 49. Springer, New York, 185\u2013212."},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01517-x"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/2159559"},{"key":"e_1_3_1_18_2","volume-title":"Linear Programming and Extensions","author":"Dantzig G. B.","year":"1963","unstructured":"G. B. Dantzig. 1963. Linear Programming and Extensions. Princeton University Press, Princeton, NJ."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/jmaa.1997.5202"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-015-9280-x"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1983.10477029"},{"key":"e_1_3_1_22_2","volume-title":"The AMPL Book","author":"Fourer R.","year":"2002","unstructured":"R. Fourer and D. Gay. 2002. The AMPL Book. Duxbury Press, Pacific Grove."},{"key":"e_1_3_1_23_2","unstructured":"Gurobi Optimization LLC. 2023. Gurobi Optimizer Reference Manual. Retrieved from https:\/\/www.gurobi.com"},{"key":"e_1_3_1_24_2","first-page":"96","article-title":"THe product of projection operators","volume":"23","author":"Halperin I.","year":"1962","unstructured":"I. Halperin. 1962. THe product of projection operators. Acta Scientiarum Mathematicarum (Szeged) 23 (1962), 96\u201399.","journal-title":"Acta Scientiarum Mathematicarum (Szeged)"},{"issue":"1","key":"e_1_3_1_25_2","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s12532-017-0130-5","article-title":"Parallelizing the dual revised simplex method","volume":"10","author":"Huangfu Q.","year":"2018","unstructured":"Q. Huangfu and J. A. J. Hall. 2018. Parallelizing the dual revised simplex method. Math. Program. Comput. 10, 1 (2018), 119\u2013142.","journal-title":"Math. Program. Comput."},{"volume-title":"ILOG CPLEX 20.1 User\u2019s Manual","year":"2020","key":"e_1_3_1_26_2","unstructured":"IBM. 2020. ILOG CPLEX 20.1 User\u2019s Manual. IBM."},{"volume-title":"ILOG CPLEX 22.1 User\u2019s Manual","year":"2022","key":"e_1_3_1_27_2","unstructured":"IBM. 2022. ILOG CPLEX 22.1 User\u2019s Manual. IBM."},{"key":"e_1_3_1_28_2","first-page":"10","volume-title":"Proceedings of the Conference on Foundations of Computer Science (FOCS\u201901)","volume":"42","author":"Indyk P.","year":"2001","unstructured":"P. Indyk. 2001. Algorithmic applications of low-distortion geometric embeddings. In Proceedings of the Conference on Foundations of Computer Science (FOCS\u201901), Vol. 42. IEEE, Washington, DC, 10\u201333."},{"key":"e_1_3_1_29_2","volume-title":"Handbook of Discrete and Computational Geometry","author":"Indyk P.","year":"2004","unstructured":"P. Indyk and J. Matou\u0161ek. 2004. Low-distortion embeddings of finite metric spaces. In Handbook of Discrete and Computational Geometry, J. Goodman and J. O\u2019Rourke (Eds.). Chapman and Hall, Boca Raton, FL."},{"key":"e_1_3_1_30_2","first-page":"604","volume-title":"Proceedings of the Symposium on the Theory of Computing (STOC\u201998)","volume":"30","author":"Indyk P.","year":"1998","unstructured":"P. Indyk and R. Motwani. 1998. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Symposium on the Theory of Computing (STOC\u201998), Vol. 30. ACM, New York, 604\u2013613."},{"issue":"3","key":"e_1_3_1_31_2","doi-asserted-by":"crossref","first-page":"Art. 31","DOI":"10.1145\/1273340.1273347","article-title":"Nearest neighbor preserving embeddings","volume":"3","author":"Indyk P.","year":"2007","unstructured":"P. Indyk and A. Naor. 2007. Nearest neighbor preserving embeddings. ACM Trans. Algor. 3, 3 (2007), Art. 31.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_1_32_2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume-title":"Proceedings of the Conference in Modern Analysis and Probability (Contemporary Mathematics)","volume":"26","author":"Johnson W.","year":"1984","unstructured":"W. Johnson and J. Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. In Proceedings of the Conference in Modern Analysis and Probability (Contemporary Mathematics), G. Hedlund (Ed.), Vol. 26. AMS, Providence, RI, 189\u2013206."},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2559902"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(89)80036-8"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/2009005"},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s11750-020-00563-0","article-title":"Distance geometry and data science","volume":"28","author":"Liberti L.","unstructured":"L. Liberti. 220. Distance geometry and data science. TOP 28 (220), 271\u2013339.","journal-title":"TOP"},{"volume-title":"Data Science and Optimization","author":"Liberti L.","key":"e_1_3_1_38_2","unstructured":"L. Liberti. pending minor revisions. Decoding noisy messages: A method that just shouldn\u2019t work. In Data Science and Optimization, A. Deza, S. Gupta, and S. Pokutta (Eds.). Fields Institute, Toronto."},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-021-01047-6"},{"key":"e_1_3_1_40_2","volume-title":"Proceedings of the 20th International Symposium on Experimental Algorithms (SEA\u201922) (LIPIcs)","volume":"233","author":"Liberti L.","year":"2022","unstructured":"L. Liberti, B. Manca, and P.-L. Poirion. 2022. Practical performance of random projections in linear programming. In Proceedings of the 20th International Symposium on Experimental Algorithms (SEA\u201922) (LIPIcs), C. Schulz and B. U\u00e7ar (Eds.), Vol. 233. Dagstuhl Publishing, Saarbr\u00fccken."},{"key":"e_1_3_1_41_2","volume-title":"Proceedings of the AIRO Optimization and Decision Science Conference (AIRO-ODS\u201922)","author":"Liberti L.","year":"2022","unstructured":"L. Liberti, B. Manca, and P.-L. Poirion. 2022. Random projections for semidefinite programming. In Proceedings of the AIRO Optimization and Decision Science Conference (AIRO-ODS\u201922), P. Cappanera et al. (Ed.). Springer, Cham."},{"key":"e_1_3_1_42_2","volume-title":"Proceedings of the Workshop Discrete Mathematics Days","author":"Liberti L.","year":"2022","unstructured":"L. Liberti, B. Manca, and P.-L. Poirion. 2022. Random projections for the distance geometry problem. In Proceedings of the Workshop Discrete Mathematics Days, M. Noy et al. (Ed.). Universidad de Cantabria, Santander."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2021.06.010"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761110"},{"key":"e_1_3_1_46_2","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1002\/rsa.20218","article-title":"On variants of the Johnson-Lindenstrauss lemma","volume":"33","author":"Matou\u0161ek J.","year":"2008","unstructured":"J. Matou\u0161ek. 2008. On variants of the Johnson-Lindenstrauss lemma. Random Struct. Algor. 33 (2008), 142\u2013156.","journal-title":"Random Struct. Algor."},{"key":"e_1_3_1_47_2","volume-title":"Lecture Notes on Metric Embeddings","author":"Matou\u0161ek J.","year":"2013","unstructured":"J. Matou\u0161ek. 2013. Lecture Notes on Metric Embeddings. Technical Report. ETH Z\u00fcrich."},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2450722"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1021106"},{"key":"e_1_3_1_50_2","volume-title":"Random Projections of Linear and Semidefinite Problems with Linear Inequalities","author":"Poirion P.-L.","year":"2020","unstructured":"P.-L. Poirion, B. F. Louren\u00e7o, and A. Takeda. 2020. Random Projections of Linear and Semidefinite Problems with Linear Inequalities. Technical Report 2007.00242."},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0094"},{"key":"e_1_3_1_52_2","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01580724","article-title":"A polynomial-time algorithm, based on Newton\u2019s method, for linear programming","volume":"40","author":"Renegar J.","year":"1988","unstructured":"J. Renegar. 1988. A polynomial-time algorithm, based on Newton\u2019s method, for linear programming. Math. Program. 40 (1988), 59\u201393.","journal-title":"Math. Program."},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1346-5"},{"key":"e_1_3_1_54_2","first-page":"775788","volume-title":"Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201920)","author":"Song Z.","year":"2020","unstructured":"Z. Song and Z. Yu. 2020. Solving tall dense linear programs in nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201920). ACM, New York, 775788."},{"key":"e_1_3_1_55_2","first-page":"9835","volume-title":"Proceedings of the 38th International Conference on Machine Learning (ICML\u201921)","volume":"139","author":"Song Z.","year":"2021","unstructured":"Z. Song and Z. Yu. 2021. Oblivious sketching-based central path method for linear programming. In Proceedings of the 38th International Conference on Machine Learning (ICML\u201921), Vol. 139. 9835\u20139847."},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1111590"},{"key":"e_1_3_1_57_2","volume-title":"Python Language Reference, version 3","author":"Rossum G. van","year":"2019","unstructured":"G. van Rossum and et al.2019. Python Language Reference, version 3. Python Software Foundation."},{"key":"e_1_3_1_58_2","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume-title":"The Random Projection Method","author":"Vempala S.","year":"2004","unstructured":"S. Vempala. 2004. The Random Projection Method. Number 65 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS, Providence, RI."},{"key":"e_1_3_1_59_2","first-page":"164","volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX)","volume":"13","author":"Venkatasubramanian S.","year":"2011","unstructured":"S. Venkatasubramanian and Q. Wang. 2011. The Johnson-Lindenstrauss transform: An empirical study. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), Vol. 13. SIAM, Providence, RI, 164\u2013173."},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_1_62_2","series-title":"Annals of Mathematics Studies","doi-asserted-by":"crossref","DOI":"10.1515\/9781400881895","volume-title":"Functional Operators. Volume II: The Geometry of Orthogonal Spaces","author":"Neumann J. von","year":"1950","unstructured":"J. von Neumann. 1950. Functional Operators. Volume II: The Geometry of Orthogonal Spaces. Number 22 in Annals of Mathematics Studies. Princeton University Press, Princeton, NJ."},{"key":"e_1_3_1_63_2","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1007\/978-3-030-17953-3_33","volume-title":"Proceedings of the Integer Programming and Combinatorial Optimization (IPCO\u201919) (LNCS)","volume":"11480","author":"Vu K.","year":"2019","unstructured":"K. Vu, P.-L. Poirion, C. D\u2019Ambrosio, and L. Liberti. 2019. Random projections for quadratic programs over a Euclidean ball. In Proceedings of the Integer Programming and Combinatorial Optimization (IPCO\u201919) (LNCS), A. Lodiet al. (Eds.), Vol. 11480. Springer, New York, NY, 442\u2013452."},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0894"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.08.025"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1137\/130919258"},{"key":"e_1_3_1_68_2","first-page":"135","volume-title":"Proceedings of the Conference on Learning Theory (COLT\u201913) (Proceedings of Machine Learning Research)","volume":"30","author":"Zhang L.","year":"2013","unstructured":"L. Zhang, M. Mahdavi, R. Jin, T. Yang, and S. Zhu. 2013. Recovering the optimal solution by dual random projection. In Proceedings of the Conference on Learning Theory (COLT\u201913) (Proceedings of Machine Learning Research), S. Shalev-Shwartz and I. Steinwart (Eds.), Vol. 30. \\(\\langle\\) jmlr.org \\(\\rangle\\) , 135\u2013157."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617506","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:45:58Z","timestamp":1750178758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,14]]},"references-count":67,"alternative-id":["10.1145\/3617506"],"URL":"https:\/\/doi.org\/10.1145\/3617506","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2023,10,14]]}}}