## 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*. Here we are interested in computing the sequence of all_{n,n}, k ≤ n*k*-assignments,*k=1,...,n*. By applying the algorithm of Gassner and Klinz (2010) for the parametric assignment problem one can compute in time*O(n*the set of^{3})*k*-assignments for those integers*k*≤*n*which refer to essential terms of the full characteristic maxpolynomial χ_{W}*(x)*of the corresponding max-plus weight matrix*W*. We show that χ_{W}*(x)*is in full canonical form, which implies that the remaining*k*-assignments refer to semi-essential terms of χ_{W}*(x)*. This property enables us to efficiently compute in time*O(n*all the remaining^{2})*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*O(n*,which is the best known time for this problem.}^{3})Original language | English |
---|---|

Pages (from-to) | 1265-1283 |

Number of pages | 19 |

Journal | Journal of Combinatorial Optimization |

Volume | 44 |

Issue number | 2 |

Early online date | 24 Jul 2022 |

DOIs | |

Publication status | Published - Sept 2022 |

## Keywords

- k-cardinality assignment problem
- max-plus algebra
- Full characteristic maxpolynomial
- Max-plus algebra
- Parametric assignment algorithm

## ASJC Scopus subject areas

- Control and Optimization
- Applied Mathematics
- Discrete Mathematics and Combinatorics
- Computer Science Applications
- Computational Theory and Mathematics