{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T16:14:31Z","timestamp":1746634471872,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T00:00:00Z","timestamp":1676505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T00:00:00Z","timestamp":1676505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000086","name":"Directorate for Mathematical and Physical Sciences","doi-asserted-by":"publisher","award":["2112311","1906451"],"award-info":[{"award-number":["2112311","1906451"]}],"id":[{"id":"10.13039\/100000086","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,11]]},"DOI":"10.1007\/s10107-023-01932-w","type":"journal-article","created":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T16:02:31Z","timestamp":1676563351000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient joint object matching via linear programming"],"prefix":"10.1007","volume":"202","author":[{"given":"Antonio","family":"De Rosa","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7097-1676","authenticated-orcid":false,"given":"Aida","family":"Khajavirad","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,16]]},"reference":[{"key":"1932_CR1","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1109\/TIT.2015.2490670","volume":"62","author":"E Abbe","year":"2016","unstructured":"Abbe, E., Bandeira, A.S., Hall, G.: Exact recovery in the stochastic block model. IEEE Trans. Inf. Theory 62, 471\u2013487 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1932_CR2","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/2001269.2001293","volume":"54","author":"S Agarwal","year":"2011","unstructured":"Agarwal, S., Furukawa, Y., Snavely, N., Simon, I., Curless, B., Seitz, S.M., Szeliski, R.: Building Rome in a day. Commun. ACM 54, 10 (2011)","journal-title":"Commun. ACM"},{"key":"1932_CR3","unstructured":"Bajaj, C., Gao, T., He, Z., Huang, Q., Liang, Z.: Smac: simultaneous mapping and clustering using spectral decompositions. In: Proceedings of the 35th International Conference on Machine Learning (PMLR), Vol. 80, pp. 324\u2013333 (2018)"},{"key":"1932_CR4","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0166-218X(86)90065-X","volume":"13","author":"F Barahona","year":"1986","unstructured":"Barahona, F.: A solvable case of quadratic $$0-1$$ programming. Discret. Appl. Math. 13, 23\u201326 (1986)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1932_CR5","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"123","author":"E Boros","year":"2002","unstructured":"Boros, E., Hammer, P.L.: Pseudo-Boolean optimization. Discret. Appl. Math. 123(1), 155\u2013225 (2002)","journal-title":"Discret. Appl. Math."},{"key":"1932_CR6","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10107-004-0564-1","volume":"103","author":"S Burer","year":"2005","unstructured":"Burer, S., Monteiro, R.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103, 427\u2013444 (2005)","journal-title":"Math. Program."},{"key":"1932_CR7","unstructured":"Chen, Y., Guibas, L., Huang, Q.: Near-optimal joint object matching via convex relaxation. In: Proceedings of the 31st International Conference on Machine Learning, Vol. 32, No. 2, pp. 100\u2013108 (2014)"},{"key":"1932_CR8","doi-asserted-by":"publisher","first-page":"5881","DOI":"10.1109\/TIT.2016.2600566","volume":"62","author":"Y Chen","year":"2016","unstructured":"Chen, Y., Suh, C., Goldsmith, A.J.: Information recovery from pairwise measurements. IEEE Trans. Inf. Theory 62, 5881\u20135905 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1932_CR9","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF01581239","volume":"59","author":"S Chopra","year":"1993","unstructured":"Chopra, S., Rao, M.R.: The partition problem. Math. Program. 59, 87\u2013115 (1993)","journal-title":"Math. Program."},{"issue":"3","key":"1932_CR10","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1109\/99.714603","volume":"5","author":"J Czyzyk","year":"1998","unstructured":"Czyzyk, J., Mesnier, M.P., More, J.J.: The neos server. IEEE J. Comput. Sci. Eng. 5(3), 68\u201375 (1998)","journal-title":"IEEE J. Comput. Sci. Eng."},{"key":"1932_CR11","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1137\/20M1348601","volume":"32","author":"A De Rosa","year":"2022","unstructured":"De Rosa, A., Khajavirad, A.: The ratio-cut polytope and K-means clustering. SIAM J. Optim. 32, 173\u2013203 (2022)","journal-title":"SIAM J. Optim."},{"key":"1932_CR12","unstructured":"Del Pia, A., Khajavirad, A.: Rank-one Boolean tensor factorization and the multilinear polytope. arXiv:2202.07053 (2022)"},{"key":"1932_CR13","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.1282","author":"A Del Pia","year":"2022","unstructured":"Del Pia, A., Khajavirad, A., Kunisky, D.: Linear programming and community detection. Math. Oper. Res. (2022). https:\/\/doi.org\/10.1287\/moor.2022.1282","journal-title":"Math. Oper. Res."},{"key":"1932_CR14","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s11263-006-6993-y","volume":"69","author":"MF Demirci","year":"2006","unstructured":"Demirci, M.F., Shokoufandeh, A., Keselman, L., Abd Bretzner, Y., Dickinson, S.: Object recognition as many-to-many feature matching. Int. J. Comput. Vis. 69, 203\u2013222 (2006)","journal-title":"Int. J. Comput. Vis."},{"issue":"2","key":"1932_CR15","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1137\/15M1020575","volume":"59","author":"I Dunning","year":"2017","unstructured":"Dunning, I., Huchette, J., Lubin, M.: JuMP: a modeling language for mathematical optimization. SIAM Rev. 59(2), 295\u2013320 (2017)","journal-title":"SIAM Rev."},{"key":"1932_CR16","unstructured":"Eisenblatter, A.: Frequency assignment in gsm networks: models, heuristics, and lower bounds. Ph.D. thesis, Technical Universityof Berlin (2001)"},{"key":"1932_CR17","series-title":"Princeton Mathematical Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Princeton Mathematical Series, Springer, Berlin, New York (1988)"},{"key":"1932_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF01580870","volume":"47","author":"M Gr\u00f6tschel","year":"1990","unstructured":"Gr\u00f6tschel, M., Wakabayashi, Y.: Facets of the clique partitioning polytope. Math. Program. 47, 367\u2013387 (1990)","journal-title":"Math. Program."},{"key":"1932_CR19","unstructured":"Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual (2021)"},{"issue":"5","key":"1932_CR20","doi-asserted-by":"publisher","first-page":"2788","DOI":"10.1109\/TIT.2016.2546280","volume":"62","author":"B Hajek","year":"2016","unstructured":"Hajek, B., Wu, Y., Xu, J.: Achieving exact cluster recovery threshold via semidefinite programming. IEEE Trans. Inf. Theory 62(5), 2788\u20132797 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"1932_CR21","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF02612354","volume":"28","author":"PL Hammer","year":"1984","unstructured":"Hammer, P.L., Hansen, P., Simeone, B.: Roof duality, complementation and persistency in quadratic 0\u20131 optimization. Math. Program. 28(2), 121\u2013155 (1984)","journal-title":"Math. Program."},{"key":"1932_CR22","doi-asserted-by":"crossref","unstructured":"Hu, N., Huang, Q., Thibert, B., Guibas, L.J.: Distributable consistent multi-object matching. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2463\u20132471 (2018)","DOI":"10.1109\/CVPR.2018.00261"},{"issue":"5","key":"1932_CR23","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1111\/cgf.12184","volume":"32","author":"Q-X Huang","year":"2013","unstructured":"Huang, Q.-X., Guibas, L.: Consistent shape maps via semidefinite programming. Comput. Graph. Forum 32(5), 177\u2013186 (2013)","journal-title":"Comput. Graph. Forum"},{"key":"1932_CR24","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s12532-018-0138-5","volume":"10","author":"A Khajavirad","year":"2018","unstructured":"Khajavirad, A., Sahinidis, N.V.: A hybrid LP\/NLP paradigm for global optimization relaxations. Math. Program. Comput. 10, 383\u2013421 (2018)","journal-title":"Math. Program. Comput."},{"key":"1932_CR25","unstructured":"Li, Y., Gu, C., Dullien, T., Vinyals, O., Kohli, P.: Graph matching networks for learning the similarity of graph structured objects. In: Proceedings of the 36th International Conference on Machine Learning (PMLR), Vol. 97, pp. 3835\u20133845 (2019)"},{"key":"1932_CR26","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.acha.2022.02.003","volume":"60","author":"S Ling","year":"2022","unstructured":"Ling, S.: Near-optimal performance bounds for orthogonal and permutation group synchronization via spectral methods. Appl. Comput. Harmon. Anal. 60, 20\u201352 (2022)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1932_CR27","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0024-3795(79)90014-4","volume":"25","author":"OL Mangasarian","year":"1979","unstructured":"Mangasarian, O.L.: Uniqueness of solution in linear programming. Linear Algebra Appl. 25, 151\u2013162 (1979)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"1932_CR28","doi-asserted-by":"publisher","first-page":"2908","DOI":"10.1137\/20M1318523","volume":"35","author":"C Michini","year":"2021","unstructured":"Michini, C.: Tight cycle relaxations for the cut polytope. SIAM J. Discret. Math. 35(4), 2908\u20132921 (2021)","journal-title":"SIAM J. Discret. Math."},{"key":"1932_CR29","doi-asserted-by":"crossref","unstructured":"Moitra, A., Perry, W., Wein, A. S.: How robust are reconstruction thresholds for community detection? In: STOC \u201916: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pp. 828\u2013841 (2016)","DOI":"10.1145\/2897518.2897573"},{"key":"1932_CR30","unstructured":"MOSEK 9.2. http:\/\/docs.mosek.com\/9.0\/faq.pdf (2019)"},{"key":"1932_CR31","unstructured":"Pachauri, D., Kondor, R., Sargur, G., Singh, V.: Permutation diffusion maps with application to the image association problem in computer vision. In: Advances in Neural Information Processing Systems, pp. 541\u2013549 (2014)"},{"key":"1932_CR32","unstructured":"Pachauri, D., Kondor, R., Singh, V.: Solving the multi-way matching problem by permutation synchronization. In: Advances in Neural Information Processing Systems, pp. 1860\u20131868 (2013)"},{"key":"1932_CR33","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M Padberg","year":"1989","unstructured":"Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45, 139\u2013172 (1989)","journal-title":"Math. Program."},{"key":"1932_CR34","doi-asserted-by":"publisher","first-page":"12015","DOI":"10.1088\/1742-6596\/699\/1\/012015","volume":"699","author":"F Ricci-Tersenghi","year":"2016","unstructured":"Ricci-Tersenghi, F., Javanmard, A., Montanari, A.: Performance of a community detection algorithm based on semidefinite programming. J. Phys. Conf. Ser. 699, 12015\u201312025 (2016)","journal-title":"J. Phys. Conf. Ser."},{"key":"1932_CR35","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Chichester (1986)"},{"key":"1932_CR36","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80, 346\u2013355 (2000)","journal-title":"J. Combin. Theory Ser. B"},{"key":"1932_CR37","unstructured":"Shen, Y., Huang, Q., Srebro, N., Sanghavi, S.: Normalized spectral map synchronization. In: Advances in Neural Information Processing Systems, pp. 4925\u20134933 (2016)"},{"key":"1932_CR38","volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47. Cambridge University Press, Cambridge (2018)"},{"key":"1932_CR39","doi-asserted-by":"crossref","unstructured":"Yan, J., Yang, S., Hancock, E. R.: Learning for graph matching and related combinatorial optimization problems. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20), pp. 4988\u20134996 (2020)","DOI":"10.24963\/ijcai.2020\/694"},{"key":"1932_CR40","doi-asserted-by":"crossref","unstructured":"Zhou, X., Zhu, M., Daniilidis, K.: Multi-image matching via fast alternating minimization. In: Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 4032\u20134040 (2015)","DOI":"10.1109\/ICCV.2015.459"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01932-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01932-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01932-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T19:52:30Z","timestamp":1697053950000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01932-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,16]]},"references-count":40,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["1932"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01932-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,2,16]]},"assertion":[{"value":"26 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}