{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:54:35Z","timestamp":1758268475354,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,7,24]],"date-time":"2022-07-24T00:00:00Z","timestamp":1658620800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,24]],"date-time":"2022-07-24T00:00:00Z","timestamp":1658620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P29355-N35"],"award-info":[{"award-number":["P29355-N35"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,9]]},"abstract":"Abstract<\/jats:title>The k<\/jats:italic>-cardinality assignment (k<\/jats:italic>-assignment, for short) problem asks for finding a minimal (maximal) weight of a matching of cardinality k<\/jats:italic> in a weighted bipartite graph $$K_{n,n}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \n n<\/mml:mi>\n ,<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$k \\le n$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \u2264<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Here we are interested in computing the sequence of all k<\/jats:italic>-assignments, $$k=1,\\ldots ,n$$<\/jats:tex-math>\n \n k<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. By applying the algorithm of Gassner and Klinz (2010) for the parametric assignment problem one can compute in time $${\\mathcal {O}}(n^3)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> the set of k<\/jats:italic>-assignments for those integers $$k \\le n$$<\/jats:tex-math>\n \n k<\/mml:mi>\n \u2264<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> which refer to essential terms of the full characteristic maxpolynomial $${\\bar{\\chi }}_{W}(x)$$<\/jats:tex-math>\n \n \n \n \n \u03c7<\/mml:mi>\n <\/mml:mrow>\n \n \u00af<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mover>\n W<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the corresponding max-plus weight matrix W<\/jats:italic>. We show that $${\\bar{\\chi }}_{W}(x)$$<\/jats:tex-math>\n \n \n \n \n \u03c7<\/mml:mi>\n <\/mml:mrow>\n \n \u00af<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mover>\n W<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is in full canonical form, which implies that the remaining k<\/jats:italic>-assignments refer to semi-essential terms of $${\\bar{\\chi }}_{W}(x)$$<\/jats:tex-math>\n \n \n \n \n \u03c7<\/mml:mi>\n <\/mml:mrow>\n \n \u00af<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mover>\n W<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This property enables us to efficiently compute in time $${\\mathcal {O}}(n^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> all the remaining k<\/jats:italic>-assignments out of the already computed essential k<\/jats:italic>-assignments. It follows that time complexity for computing the sequence of all k<\/jats:italic>-cardinality assignments is $${\\mathcal {O}}(n^3)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is the best known time for this problem. \n<\/jats:p>","DOI":"10.1007\/s10878-022-00889-4","type":"journal-article","created":{"date-parts":[[2022,7,24]],"date-time":"2022-07-24T17:02:15Z","timestamp":1658682135000},"page":"1265-1283","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computing the sequence of k-cardinality assignments"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0255-0885","authenticated-orcid":false,"given":"Amnon","family":"Rosenmann","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,24]]},"reference":[{"key":"889_CR1","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows (Prentice Hall, Inc., Englewood Cliffs, NJ), pp. xvi+846. Theory, algorithms, and applications"},{"key":"889_CR2","doi-asserted-by":"crossref","unstructured":"Akian M, Bapat R, Gaubert S (2001) Generic asymptotics of eigenvalues using Min-Plus algebra. In: Proceedings of the Workshop on Max-Plus Algebras, IFAC SSSC\u201901","DOI":"10.1016\/S1474-6670(17)39090-0"},{"key":"889_CR3","doi-asserted-by":"crossref","unstructured":"Bai Gz (2009) A new algorithm for k-cardinality assignment problem. In: Proceedings of the 2009 International Conference on Computational Intelligence and Software Engineering (CiSE), Wuhan, China","DOI":"10.1109\/CISE.2009.5363717"},{"issue":"1","key":"889_CR4","first-page":"75","volume":"37","author":"I Belik","year":"2016","unstructured":"Belik I, J\u00f6rnsten K (2016) A new semi-Lagrangean relaxation for the $$k$$-cardinality assignment problem. J Inf Optim Sci 37(1):75\u2013100","journal-title":"J Inf Optim Sci"},{"issue":"1","key":"889_CR5","first-page":"62","volume":"27","author":"AK Bhunia","year":"2017","unstructured":"Bhunia AK, Biswas A, Samanta SS (2017) A genetic algorithm-based approach for unbalanced assignment problem in interval environment. Int J Log Syst Manag 27(1):62\u201377","journal-title":"Int J Log Syst Manag"},{"key":"889_CR6","doi-asserted-by":"crossref","unstructured":"Burkard R, Dell\u2019Amico M, Martello S (2012) Assignment problems (Revised Reprint) (Society for Industrial and Applied Mathematics (SIAM), 2012)","DOI":"10.1137\/1.9781611972238"},{"key":"889_CR7","series-title":"In: Springer Monographs in Mathematics","doi-asserted-by":"publisher","first-page":"xviii+272","DOI":"10.1007\/978-1-84996-299-5","volume-title":"Max-linear Systems: Theory and Algorithms","author":"P Butkovi\u010d","year":"2010","unstructured":"Butkovi\u010d P (2010) Max-linear Systems: Theory and Algorithms. In: Springer Monographs in Mathematics. Springer-Verlag, London Ltd., London, p xviii+272"},{"issue":"1","key":"889_CR8","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BF02591893","volume":"26","author":"PJ Carstensen","year":"1983","unstructured":"Carstensen PJ (1983) Complexity of some parametric integer and network programming problems. Math Programming 26(1):64\u201375. https:\/\/doi.org\/10.1007\/BF02591893","journal-title":"Math Programming"},{"issue":"1","key":"889_CR9","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/0022-247X(83)90139-7","volume":"95","author":"RA Cuninghame-Green","year":"1983","unstructured":"Cuninghame-Green RA (1983) The characteristic maxpolynomial of a matrix. J Math Anal Appl 95(1):110\u2013116","journal-title":"J Math Anal Appl"},{"issue":"4","key":"889_CR10","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0166-218X(80)90025-6","volume":"2","author":"RA Cuninghame-Green","year":"1980","unstructured":"Cuninghame-Green RA, Meijer PFJ (1980) An algebra for piecewise-linear minimax problems. Discrete Appl Math 2(4):267\u2013294","journal-title":"Discrete Appl Math"},{"key":"889_CR11","doi-asserted-by":"publisher","unstructured":"De\u00a0Schutter B, De\u00a0Moor B (2002) The QR decomposition and the singular value decomposition in the symmetrized max-plus algebra revisited. SIAM Rev. 44(3), 417\u2013454 (2002). Reprint of SIAM J. Matrix Anal. App. 19(2), 378\u2013406 (1998) (electronic), https:\/\/doi.org\/10.1137\/S00361445024039","DOI":"10.1137\/S00361445024039"},{"issue":"1","key":"889_CR12","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0166-218X(00)00301-2","volume":"110","author":"M Dell\u2019Amico","year":"2001","unstructured":"Dell\u2019Amico M, Lodi A, Martello S (2001) Efficient algorithms and codes for $$k$$-cardinality assignment problems. Discrete Appl Math 110(1):25\u201340","journal-title":"Discrete Appl Math"},{"key":"889_CR13","doi-asserted-by":"publisher","unstructured":"Dell\u2019Amico M, Martello S (1997) The $$k$$-cardinality assignment problem. Discrete Appl. Math. 76(1-3), 103\u2013121. Second International Colloquium on Graphs and Optimization (Leukerbad, 1994), https:\/\/doi.org\/10.1016\/S0166-218X(97)00120-0","DOI":"10.1016\/S0166-218X(97)00120-0"},{"issue":"2","key":"889_CR14","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. J ACM 19(2):248\u2013264. https:\/\/doi.org\/10.1145\/321694.321699","journal-title":"J ACM"},{"key":"889_CR15","first-page":"16","volume":"38","author":"J Egerv\u00e1ry","year":"1931","unstructured":"Egerv\u00e1ry J (1931) Matrixok kombinatorius tulajdons\u00e1gair\u00f3l (in Hungarian) [On combinatorial properties of matrices]. Matematikai \u00e9s Fizikai Lapok 38:16\u201328","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"issue":"3","key":"889_CR16","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J Assoc Comput Mach 34(3):596\u2013615. https:\/\/doi.org\/10.1145\/28869.28874","journal-title":"J Assoc Comput Mach"},{"issue":"2","key":"889_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/net.20288","volume":"55","author":"E Gassner","year":"2010","unstructured":"Gassner E, Klinz B (2010) A fast parametric assignment algorithm with applications in max-algebra. Networks 55(2):61\u201377. https:\/\/doi.org\/10.1002\/net.20288","journal-title":"Networks"},{"key":"889_CR18","unstructured":"Hook J (2016) An algorithm for computing the eiginvalues of a max-plus matrix polynomial. preprint at http:\/\/eprints.maths.manchester.ac.uk\/"},{"key":"889_CR19","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.laa.2015.08.019","volume":"486","author":"J Hook","year":"2015","unstructured":"Hook J (2015) Max-plus singular values. Linear Algebra Appl 486:419\u2013442. https:\/\/doi.org\/10.1016\/j.laa.2015.08.019","journal-title":"Linear Algebra Appl"},{"issue":"1","key":"889_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","volume":"3","author":"RM Karp","year":"1981","unstructured":"Karp RM, Orlin JB (1981) Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl Math 3(1):37\u201345. https:\/\/doi.org\/10.1016\/0166-218X(81)90026-3","journal-title":"Discrete Appl Math"},{"issue":"4","key":"889_CR21","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u00f6nig","year":"1916","unstructured":"K\u00f6nig D (1916) \u00dcber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math Ann 77(4):453\u2013465. https:\/\/doi.org\/10.1007\/BF01456961","journal-title":"Math Ann"},{"key":"889_CR22","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res Logist Quart 2:83\u201397. https:\/\/doi.org\/10.1002\/nav.3800020109","journal-title":"Naval Res Logist Quart"},{"issue":"1957","key":"889_CR23","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/nav.3800030404","volume":"3","author":"HW Kuhn","year":"1956","unstructured":"Kuhn HW (1956) Variants of the Hungarian method for assignment problems. Naval Res Logist Quart 3(1957):253\u2013258. https:\/\/doi.org\/10.1002\/nav.3800030404","journal-title":"Naval Res Logist Quart"},{"issue":"3","key":"889_CR24","doi-asserted-by":"publisher","first-page":"301","DOI":"10.5267\/j.dsl.2017.7.002","volume":"7","author":"T Kumar","year":"2018","unstructured":"Kumar T, Purusotham S (2018) The degree constrained k-cardinality minimum spanning tree problem: a lexi-search algorithm. Decision Science Letters 7(3):301\u2013310","journal-title":"Decision Science Letters"},{"key":"889_CR25","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1137\/0105003","volume":"5","author":"J Munkres","year":"1957","unstructured":"Munkres J (1957) Algorithms for the assignment and transportation problems. J Soc Indust Appl Math 5:32\u201338","journal-title":"J Soc Indust Appl Math"},{"key":"889_CR26","unstructured":"Murty KG (1983) Linear programming (John Wiley & Sons, Inc., New York), p xix+482. With a foreword by George B. Dantzig"},{"issue":"2","key":"889_CR27","doi-asserted-by":"publisher","first-page":"267","DOI":"10.5267\/j.ijiec.2021.10.002","volume":"13","author":"A Prakash","year":"2022","unstructured":"Prakash A, Balakrishna U, Thenepalle JKT (2022) An exact algorithm for constrained k-cardinality unbalanced assignment problem. Int J Ind Eng Comput 13(2):267\u2013276. https:\/\/doi.org\/10.5267\/j.ijiec.2021.10.002","journal-title":"Int J Ind Eng Comput"},{"key":"889_CR28","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1016\/j.laa.2019.05.020","volume":"578","author":"A Rosenmann","year":"2019","unstructured":"Rosenmann A, Lehner F, Peperko A (2019) Polynomial convolutions in max-plus algebra. Linear Algebra Appl 578:370\u2013401. https:\/\/doi.org\/10.1016\/j.laa.2019.05.020","journal-title":"Linear Algebra Appl"},{"key":"889_CR29","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/net.3230010206","volume":"1","author":"N Tomizawa","year":"1971","unstructured":"Tomizawa N (1971) On some techniques useful for solution of transportation network problems. Networks 1:173\u2013194. https:\/\/doi.org\/10.1002\/net.3230010206","journal-title":"Networks"},{"issue":"2","key":"889_CR30","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/S0377-2217(03)00205-4","volume":"157","author":"A Volgenant","year":"2004","unstructured":"Volgenant A (2004) Solving the $$k$$-cardinality assignment problem by transformation. European J Oper Res 157(2):322\u2013331. https:\/\/doi.org\/10.1016\/S0377-2217(03)00205-4","journal-title":"European J Oper Res"},{"issue":"2","key":"889_CR31","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230210206","volume":"21","author":"NE Young","year":"1991","unstructured":"Young NE, Tarjan RE, Orlin JB (1991) Faster parametric shortest path and minimum-balance algorithms. Networks 21(2):205\u2013221. https:\/\/doi.org\/10.1002\/net.3230210206","journal-title":"Networks"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00889-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00889-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00889-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T06:20:46Z","timestamp":1660371646000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00889-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,24]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["889"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00889-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,7,24]]},"assertion":[{"value":"15 July 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2022","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 not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}},{"value":"The author has no financial or proprietary interests in any material discussed in this article.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Financial interests"}}]}}