Cover Image

Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem

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 w...

Full description

Saved in:
Bibliographic Details
Main Authors: Dlask, Tomáš (Author) , Savchynskyy, Bogdan (Author)
Format: Article (Journal)
Language:English
Published: 21 May 2025
In: Annals of mathematics and artificial intelligence

ISSN:1573-7470
DOI:10.1007/s10472-025-09974-w
Online Access:Verlag, kostenfrei, Volltext: https://doi.org/10.1007/s10472-025-09974-w
Verlag, kostenfrei, Volltext: https://link.springer.com/article/10.1007/s10472-025-09974-w
Get full text
Author Notes:Tomáš Dlask, Bogdan Savchynskyy

MARC

LEADER 00000naa a22000002c 4500
001 1939370019
003 DE-627
005 20251023182946.0
007 cr uuu---uuuuu
008 251023s2025 xx |||||o 00| ||eng c
024 7 |a 10.1007/s10472-025-09974-w  |2 doi 
035 |a (DE-627)1939370019 
035 |a (DE-599)KXP1939370019 
040 |a DE-627  |b ger  |c DE-627  |e rda 
041 |a eng 
084 |a 27  |2 sdnb 
100 1 |a Dlask, Tomáš  |e VerfasserIn  |0 (DE-588)1379716721  |0 (DE-627)1939370124  |4 aut 
245 1 0 |a Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem  |c Tomáš Dlask, Bogdan Savchynskyy 
264 1 |c 21 May 2025 
336 |a Text  |b txt  |2 rdacontent 
337 |a Computermedien  |b c  |2 rdamedia 
338 |a Online-Ressource  |b cr  |2 rdacarrier 
500 |a Gesehen am 23.10.2025 
520 |a 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. 
650 4 |a Block-coordinate ascent 
650 4 |a Linear assignment problem 
650 4 |a Quadratic assignment problem 
650 4 |a Relative interior 
700 1 |a Savchynskyy, Bogdan  |e VerfasserIn  |0 (DE-588)1066503605  |0 (DE-627)817659439  |0 (DE-576)426018737  |4 aut 
773 0 8 |i Enthalten in  |t Annals of mathematics and artificial intelligence  |d Dordrecht [u.a.] : Springer Science + Business Media B.V, 1990  |g (2025) Early Access, 44 Seiten  |h Online-Ressource  |w (DE-627)320424154  |w (DE-600)2002961-5  |w (DE-576)110279190  |x 1573-7470  |7 nnas  |a Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem 
773 1 8 |g year:2025  |a Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem 
856 4 0 |u https://doi.org/10.1007/s10472-025-09974-w  |x Verlag  |x Resolving-System  |z kostenfrei  |3 Volltext 
856 4 0 |u https://link.springer.com/article/10.1007/s10472-025-09974-w  |x Verlag  |z kostenfrei  |3 Volltext 
951 |a AR 
992 |a 20251023 
993 |a Article 
994 |a 2025 
998 |g 1066503605  |a Savchynskyy, Bogdan  |m 1066503605:Savchynskyy, Bogdan  |d 700000  |d 708000  |e 700000PS1066503605  |e 708000PS1066503605  |k 0/700000/  |k 1/700000/708000/  |p 2  |y j 
999 |a KXP-PPN1939370019  |e 479104150X 
BIB |a Y 
SER |a journal 
JSO |a {"note":["Gesehen am 23.10.2025"],"type":{"media":"Online-Ressource","bibl":"article-journal"},"language":["eng"],"relHost":[{"title":[{"title":"Annals of mathematics and artificial intelligence","title_sort":"Annals of mathematics and artificial intelligence"}],"pubHistory":["1.1990 -"],"part":{"issue":"44 Seiten","year":"2025","text":"(2025) Early Access, 44 Seiten","volume":"(2025) Early Access"},"note":["Gesehen am 31.10.05"],"disp":"Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problemAnnals of mathematics and artificial intelligence","type":{"bibl":"periodical","media":"Online-Ressource"},"recId":"320424154","language":["eng"],"origin":[{"dateIssuedDisp":"1990-","publisher":"Springer Science + Business Media B.V ; Baltzer Science Publ. ; Kluwer","dateIssuedKey":"1990","publisherPlace":"Dordrecht [u.a.] ; Bussum ; Dordrecht [u.a.]"}],"id":{"issn":["1573-7470"],"zdb":["2002961-5"],"eki":["320424154"]},"physDesc":[{"extent":"Online-Ressource"}]}],"recId":"1939370019","person":[{"family":"Dlask","given":"Tomáš","display":"Dlask, Tomáš","roleDisplay":"VerfasserIn","role":"aut"},{"display":"Savchynskyy, Bogdan","roleDisplay":"VerfasserIn","role":"aut","family":"Savchynskyy","given":"Bogdan"}],"name":{"displayForm":["Tomáš Dlask, Bogdan Savchynskyy"]},"origin":[{"dateIssuedKey":"2025","dateIssuedDisp":"21 May 2025"}],"title":[{"title":"Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem","title_sort":"Relative-interior solution for the (incomplete) linear assignment problem with applications to the quadratic assignment problem"}],"id":{"doi":["10.1007/s10472-025-09974-w"],"eki":["1939370019"]}} 
SRT |a DLASKTOMASRELATIVEIN2120 

Similar Items