Computing the sequence of k-cardinality assignments

Amnon Rosenmann ()
Additional contact information
Amnon Rosenmann: Graz University of Technology

Journal of Combinatorial Optimization, 2022, vol. 44, issue 2, No 18, 1265-1283

Abstract: Abstract The k-cardinality assignment (k-assignment, for short) problem asks for finding a minimal (maximal) weight of a matching of cardinality k in a weighted bipartite graph $$K_{n,n}$$ K n , n , $$k \le n$$ k ≤ n . Here we are interested in computing the sequence of all k-assignments, $$k=1,\ldots ,n$$ k = 1 , … , n . By applying the algorithm of Gassner and Klinz (2010) for the parametric assignment problem one can compute in time $${\mathcal {O}}(n^3)$$ O ( n 3 ) the set of k-assignments for those integers $$k \le n$$ k ≤ n which refer to essential terms of the full characteristic maxpolynomial $${\bar{\chi }}_{W}(x)$$ χ ¯ W ( x ) of the corresponding max-plus weight matrix W. We show that $${\bar{\chi }}_{W}(x)$$ χ ¯ W ( x ) is in full canonical form, which implies that the remaining k-assignments refer to semi-essential terms of $${\bar{\chi }}_{W}(x)$$ χ ¯ W ( x ) . This property enables us to efficiently compute in time $${\mathcal {O}}(n^2)$$ O ( n 2 ) all the remaining k-assignments out of the already computed essential k-assignments. It follows that time complexity for computing the sequence of all k-cardinality assignments is $${\mathcal {O}}(n^3)$$ O ( n 3 ) , which is the best known time for this problem.

Keywords: k-cardinality assignment problem; Parametric assignment algorithm; Max-plus algebra; Full characteristic maxpolynomial; 90C10; 15A80; 15A15 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00889-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:2:d:10.1007_s10878-022-00889-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00889-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().