Computing the sequence of k-cardinality assignments.

Area of Science:

• Combinatorial Optimization
• Graph Theory
• Algorithm Design

Background:

• The k-cardinality assignment problem seeks to find the minimal or maximal weight of a matching with cardinality k in a weighted bipartite graph.
• Computing the entire sequence of k-assignments is computationally challenging.

Purpose of the Study:

• To develop an efficient method for computing the complete sequence of k-assignments.
• To improve the time complexity for solving the k-cardinality assignment problem.

Main Methods:

• Leveraging the Gassner and Klinz algorithm for the parametric assignment problem.
• Utilizing the properties of the max-plus weight matrix and its characteristic maxpolynomial.
• Exploiting the canonical form of the maxpolynomial to efficiently compute remaining k-assignments from essential ones.

Main Results:

• An efficient algorithm is presented to compute essential k-assignments in O(n^3) time.
• The structure of the maxpolynomial allows for the computation of all remaining k-assignments in O(n^2) time.
• The overall time complexity for computing the sequence of all k-assignments is reduced to O(n^3).

Conclusions:

• The proposed method achieves the best known time complexity for computing all k-cardinality assignments.
• This advancement offers a significant improvement for solving problems related to weighted bipartite matching.