{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T15:30:46Z","timestamp":1769873446865,"version":"3.49.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T00:00:00Z","timestamp":1747785600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T00:00:00Z","timestamp":1747785600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007655","name":"Czech Technical University in Prague","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We study the set of optimal solutions of the dual linear programming formulation of the linear assignment problem (LAP) to propose a method for computing a solution from the relative interior of this set. Assuming that an arbitrary dual-optimal solution and an optimal assignment are available (for which many efficient algorithms already exist), our method computes a relative-interior solution in linear time. Since the LAP occurs as a subproblem in the linear programming (LP) relaxation of the quadratic assignment problem (QAP), we employ our method as a new component in the family of dual-ascent algorithms that provide bounds on the optimal value of the QAP. To make our results applicable to the incomplete QAP, which is of interest in practical use-cases, we also provide a linear-time reduction from the incomplete LAP to the complete LAP along with a mapping that preserves optimality and membership in the relative interior. Our experiments on publicly available benchmarks indicate that our approach with relative-interior solution can frequently provide bounds near the optimum of the LP relaxation and its runtime is much lower when compared to a commercial LP solver.<\/jats:p>","DOI":"10.1007\/s10472-025-09974-w","type":"journal-article","created":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T07:48:29Z","timestamp":1747813709000},"page":"19-62","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem"],"prefix":"10.1007","volume":"94","author":[{"given":"Tom\u00e1\u0161","family":"Dlask","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bogdan","family":"Savchynskyy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,21]]},"reference":[{"key":"9974_CR1","doi-asserted-by":"crossref","unstructured":"Burkard, R., Dell\u2019Amico, M., Martello, S.: Assignment Problems. SIAM-Society of Industrial and Applied Mathematics (2009)","DOI":"10.1137\/1.9780898717754"},{"key":"9974_CR2","unstructured":"Cela, E.: The Quadratic Assignment Problem: Theory and Algorithms. vol.\u00a01. Springer Science & Business Media (2013)"},{"key":"9974_CR3","doi-asserted-by":"crossref","unstructured":"Haller, S., Feineis, L., Hutschenreiter, L., Bernard, F., Rother, C., Kainm\u00fcller, D., et\u00a0al.: A comparative study of graph matching algorithms in computer vision. In: European Conference on Computer Vision. Springer. p. 636\u2013653 (2022)","DOI":"10.1007\/978-3-031-20050-2_37"},{"issue":"4","key":"9974_CR4","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1287\/mnsc.9.4.586","volume":"9","author":"EL Lawler","year":"1963","unstructured":"Lawler, E.L.: The quadratic assignment problem. Manage. Sci. 9(4), 586\u2013599 (1963)","journal-title":"Manage. Sci."},{"issue":"4","key":"9974_CR5","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1023\/A:1008293323270","volume":"10","author":"RE Burkard","year":"1997","unstructured":"Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB-a quadratic assignment problem library. J. Global Optim. 10(4), 391\u2013403 (1997)","journal-title":"J. Global Optim."},{"key":"9974_CR6","doi-asserted-by":"crossref","unstructured":"Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica: Journal of the Econometric Society. 25, 53\u201376 (1957)","DOI":"10.2307\/1907742"},{"key":"9974_CR7","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Shi, Q., McAuley, J., Wei, W., Zhang, Y., Van Den\u00a0Hengel, A.: Pairwise matching through max-weight bipartite belief propagation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. p. 1202\u20131210 (2016)","DOI":"10.1109\/CVPR.2016.135"},{"key":"9974_CR8","doi-asserted-by":"crossref","unstructured":"Hutschenreiter, L., Haller, S., Feineis, L., Rother, C., Kainm\u00fcller, D., Savchynskyy, B.: Fusion moves for graph matching. In: Proceedings of the IEEE\/CVF International Conference on Computer Vision. p. 6270\u20136279 (2021)","DOI":"10.1109\/ICCV48922.2021.00621"},{"key":"9974_CR9","doi-asserted-by":"crossref","unstructured":"Werner, T., Pr\u016f\u0161a, D., Dlask, T.: Relative interior rule in block-coordinate descent. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition. p. 7559\u20137567 (2020)","DOI":"10.1109\/CVPR42600.2020.00758"},{"key":"9974_CR10","doi-asserted-by":"crossref","unstructured":"Savchynskyy, B.: Discrete graphical models-an optimization perspective. Foundations and Trends\u00ae in Computer Graphics and Vision. 2019;11(3-4):160\u2013429","DOI":"10.1561\/0600000084"},{"issue":"7","key":"9974_CR11","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/TPAMI.2007.1036","volume":"29","author":"T Werner","year":"2007","unstructured":"Werner, T.: A linear programming approach to max-sum problem: A review. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1165\u20131179 (2007)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1\u20132","key":"9974_CR12","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Research Logistics Quarterly. 2(1\u20132), 83\u201397 (1955)","journal-title":"Naval Research Logistics Quarterly."},{"key":"9974_CR13","unstructured":"Globerson, A., Jaakkola, T.: Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. Advances in Neural Information Processing Systems. 2007;20"},{"key":"9974_CR14","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1090\/dimacs\/016\/02","volume":"16","author":"WP Adams","year":"1994","unstructured":"Adams, W.P., Johnson, T.A.: Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 16, 43\u201377 (1994)","journal-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci."},{"issue":"2","key":"9974_CR15","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0110022","volume":"10","author":"PC Gilmore","year":"1962","unstructured":"Gilmore, P.C.: Optimal and suboptimal algorithms for the quadratic assignment problem. J. Soc. Ind. Appl. Math. 10(2), 305\u2013313 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"6","key":"9974_CR16","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1287\/opre.46.6.912","volume":"46","author":"P Hahn","year":"1998","unstructured":"Hahn, P., Grant, T.: Lower bounds for the quadratic assignment problem based upon a dual formulation. Oper. Res. 46(6), 912\u2013922 (1998)","journal-title":"Oper. Res."},{"key":"9974_CR17","first-page":"147","volume":"5","author":"G Birkhoff","year":"1946","unstructured":"Birkhoff, G.: Tres observaciones sobre el algebra lineal. Univ Nac Tucuman, Ser A. 5, 147\u2013154 (1946)","journal-title":"Univ Nac Tucuman, Ser A."},{"key":"9974_CR18","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1998","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, North Chelmsford (1998)"},{"key":"9974_CR19","volume-title":"Fundamentals of Convex Analysis","author":"JB Hiriart-Urruty","year":"2004","unstructured":"Hiriart-Urruty, J.B., Lemar\u00e9chal, C.: Fundamentals of Convex Analysis. Springer Science & Business Media, Berlin (2004)"},{"key":"9974_CR20","doi-asserted-by":"crossref","unstructured":"Zhang, S.: On the strictly complementary slackness relation in linear programming. In: Advances in Optimization and Approximation. Springer. p. 347\u2013361 (1994)","DOI":"10.1007\/978-1-4613-3629-7_19"},{"key":"9974_CR21","unstructured":"Claus, G., Cambazard, H., Jost, V.: Analysis of reduced costs filtering for alldifferent and minimum weight alldifferent global constraints. In: ECAI 2020. IOS Press. p. 323\u2013330 (2020)"},{"key":"9974_CR22","unstructured":"Mills-Tettey, G.A., Stentz, A., Dias, M.B.: The dynamic Hungarian algorithm for the assignment problem with changing costs. Robotics Institute, Pittsburgh, PA, Tech Rep CMU-RI-TR-07-27 (2007)"},{"key":"9974_CR23","doi-asserted-by":"crossref","unstructured":"Akg\u00fcl M. The linear assignment problem. In: Combinatorial optimization. Springer; 1992. p. 85\u2013122","DOI":"10.1007\/978-3-642-77489-8_5"},{"key":"9974_CR24","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.tcs.2011.12.071","volume":"423","author":"T Tassa","year":"2012","unstructured":"Tassa, T.: Finding all maximally-matchable edges in a bipartite graph. Theoret. Comput. Sci. 423, 50\u201358 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"9974_CR25","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9974_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0898-1221(81)90008-0","volume":"7","author":"M Sharir","year":"1981","unstructured":"Sharir, M.: A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications. 7(1), 67\u201372 (1981)","journal-title":"Computers & Mathematics with Applications."},{"key":"9974_CR27","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033104","volume-title":"Graphs: Theory and Algorithms","author":"K Thulasiraman","year":"1992","unstructured":"Thulasiraman, K., Swamy, M.N.: Graphs: Theory and Algorithms. John Wiley & Sons, Hoboken (1992)"},{"key":"9974_CR28","unstructured":"R\u00e9gin, J.C.: A filtering algorithm for constraints of difference in CSPs. In: Proceedings of the Twelfth AAAI National Conference on Artificial Intelligence. AAAI\u201994. AAAI Press. p. 362-367 (1994)"},{"key":"9974_CR29","doi-asserted-by":"crossref","unstructured":"German, G., Briant, O., Cambazard, H., Jost, V.: Arc consistency via linear programming. In: Principles and Practice of Constraint Programming: 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28\u2013September 1, 2017, Proceedings 23. Springer. p. 114\u2013128 (2017)","DOI":"10.1007\/978-3-319-66158-2_8"},{"issue":"10","key":"9974_CR30","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1016\/0305-0548(96)00010-X","volume":"23","author":"A Volgenant","year":"1996","unstructured":"Volgenant, A.: Linear and semi-assignment problems: a core oriented approach. Computers & Operations Research. 23(10), 917\u2013932 (1996)","journal-title":"Computers & Operations Research."},{"issue":"1","key":"9974_CR31","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s10479-010-0757-3","volume":"181","author":"J Bijsterbosch","year":"2010","unstructured":"Bijsterbosch, J., Volgenant, A.: Solving the rectangular assignment problem and applications. Ann. Oper. Res. 181(1), 443\u2013462 (2010)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"9974_CR32","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1137\/0803013","volume":"3","author":"DP Bertsekas","year":"1993","unstructured":"Bertsekas, D.P., Castanon, D.A., Tsaknakis, H.: Reverse auction and the solution of inequality constrained assignment problems. SIAM J. Optim. 3(2), 268\u2013297 (1993)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"9974_CR33","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1109\/TKDE.2016.2527003","volume":"28","author":"C Chen","year":"2016","unstructured":"Chen, C., Zheng, L., Srinivasan, V., Thomo, A., Wu, K., Sukow, A.: Conflict-aware weighted bipartite b-matching and its application to e-commerce. IEEE Trans. Knowl. Data Eng. 28(6), 1475\u20131488 (2016)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"9974_CR34","doi-asserted-by":"publisher","DOI":"10.21236\/AD0653103","volume-title":"The Symmetric Assignment Problem","author":"KG Murty","year":"1967","unstructured":"Murty, K.G.: The Symmetric Assignment Problem. California University, Berkeley Operations Research Center (1967)"},{"key":"9974_CR35","unstructured":"Ramshaw, L., Tarjan, R.E.: On minimum-cost assignments in unbalanced bipartite graphs. HP Labs, Palo Alto, CA, USA, Tech Rep HPL-2012-40R1. 2012;20"},{"issue":"12","key":"9974_CR36","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1145\/362919.362945","volume":"14","author":"F Bourgeois","year":"1971","unstructured":"Bourgeois, F., Lassalle, J.C.: An extension of the Munkres algorithm for the assignment problem to rectangular matrices. Commun. ACM 14(12), 802\u2013804 (1971)","journal-title":"Commun. ACM"},{"key":"9974_CR37","doi-asserted-by":"crossref","unstructured":"Lo, C., Kim, S., Zakov, S., Bafna, V.: Evaluating genome architecture of a complex region via generalized bipartite matching. In: BMC bioinformatics. vol.\u00a014. BioMed Central; 2013. p. 1\u201310","DOI":"10.1186\/1471-2105-14-S5-S13"},{"key":"9974_CR38","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A., et al.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Berlin (2003)"},{"key":"9974_CR39","volume-title":"Iterative Bregman Projections Algorithm for Large Sparse Incomplete Quadratic Assignment Problems [Master\u2019s thesis]","author":"H Tian","year":"2021","unstructured":"Tian, H.: Iterative Bregman Projections Algorithm for Large Sparse Incomplete Quadratic Assignment Problems [Master\u2019s thesis]. University of Heidelberg, Department of Mathematics and Computer Science (2021)"},{"key":"9974_CR40","unstructured":"Schlesinger, M.I.: Sintaksicheskiy analiz dvumernykh zritelnikh signalov v usloviyakh pomekh (Syntactic analysis of two-dimensional visual signals in noisy conditions). Kibernetika. 4(113-130) (1976)"},{"key":"9974_CR41","unstructured":"Cooper, M.C., de Givry, S., Schiex, T.: Optimal soft arc consistency. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence. vol.\u00a07. p. 68\u201373 (2007)"},{"key":"9974_CR42","doi-asserted-by":"crossref","unstructured":"Thapper, J., et\u00a0al.: The power of linear programming for valued CSPs. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. IEEE. p. 669\u2013678 (2012)","DOI":"10.1109\/FOCS.2012.25"},{"key":"9974_CR43","doi-asserted-by":"crossref","unstructured":"Pr\u016f\u0161a, D., Werner, T.: Universality of the local marginal polytope. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. p. 1738\u20131743 (2013)","DOI":"10.1109\/CVPR.2013.227"},{"key":"9974_CR44","doi-asserted-by":"crossref","unstructured":"Tourani, S., Shekhovtsov, A., Rother, C., Savchynskyy, B.: MPLP++: Fast, parallel dual block-coordinate ascent for dense graphical models. In: Proceedings of the European Conference on Computer Vision (ECCV); 2018. p. 251\u2013267","DOI":"10.1007\/978-3-030-01225-0_16"},{"issue":"7","key":"9974_CR45","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1007\/s10472-021-09731-9","volume":"90","author":"T Dlask","year":"2022","unstructured":"Dlask, T., Werner, T.: Classes of linear programs solvable by coordinate-wise minimization. Ann. Math. Artif. Intell. 90(7), 777\u2013807 (2022)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9974_CR46","unstructured":"Gurobi Optimization, LLC.: Gurobi optimizer reference manual. Available from: https:\/\/www.gurobi.com"},{"issue":"3","key":"9974_CR47","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1007\/s10589-023-00543-7","volume":"87","author":"B Beach","year":"2024","unstructured":"Beach, B., Burlacu, R., B\u00e4rmann, A., Hager, L., Hildebrand, R.: Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: Part I. Comput. Optim. Appl. 87(3), 835\u2013891 (2024)","journal-title":"Comput. Optim. Appl."},{"key":"9974_CR48","unstructured":"Cuturi, M.: Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems. 26 (2013)"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-025-09974-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-025-09974-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-025-09974-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T01:18:19Z","timestamp":1769822299000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-025-09974-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,21]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["9974"],"URL":"https:\/\/doi.org\/10.1007\/s10472-025-09974-w","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,21]]},"assertion":[{"value":"26 February 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}