Computing the sequence of k-cardinality assignments

DOI10.1007/S10878-022-00889-4zbMATH Open1493.90113arXiv2104.04037OpenAlexW3152628916MaRDI QIDQ2165282FDOQ2165282

Authors: Amnon Rosenmann 

Publication date: 19 August 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: The $k$-cardinality assignment problem asks for finding a maximal (minimal) weight of a matching of cardinality $k$ in a weighted bipartite graph $K_{n,n}$, $kleqn$. The algorithm of Gassner and Klinz from 2010 for the parametric assignment problem computes in time $O(n^3)$ the set of $k$-cardinality assignments for those integers $kleqn$ which refer to "essential" terms of a corresponding maxpolynomial. We show here that one can extend this algorithm and compute in a second stage the other "semi-essential" terms in time $O(n^2)$, which results in a time complexity of $O(n^3)$ for the whole sequence of $k=1,\mathrm{...},n$-cardinality assignments. The more there are assignments left to be computed at the second stage the faster the two-stage algorithm runs. In general, however, there is no benefit for this two-stage algorithm on the existing algorithms, e.g. the simpler network flow algorithm based on the successive shortest path algorithm which also computes all the $k$-cardinality assignments in time $O(n^3)$.

Full work available at URL: https://arxiv.org/abs/2104.04037

Recommendations

• The \(k\)-cardinality assignment problem
• A fast parametric assignment algorithm with applications in max-algebra
• Algorithms for finding a \(K\)th best valued assignment
• An algorithm for fractional assignment problems
• The \(\beta\)-assignment problems

zbMATH Keywords

max-plus algebra\(k\)-cardinality assignment problemfull characteristic maxpolynomialparametric assignment algorithm

Mathematics Subject Classification ID

Integer programming (90C10) Determinants, permanents, traces, other special matrix functions (15A15) Max-plus and related algebras (15A80)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Title not available (Why is that?)
• Fibonacci heaps and their uses in improved network optimization algorithms
• Max-linear systems. Theory and algorithms.
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On some techniques useful for solution of transportation network problems
• An algebra for piecewise-linear minimax problems
• A fast parametric assignment algorithm with applications in max-algebra
• Algorithms for the Assignment and Transportation Problems
• The characteristic maxpolynomial of a matrix
• Complexity of some parametric integer and network programming problems
• Title not available (Why is that?)
• Faster parametric shortest path and minimum‐balance algorithms
• The QR Decomposition and the Singular Value Decomposition in the Symmetrized Max-Plus Algebra
• Parametric shortest path algorithms with an application to cyclic staffing
• Title not available (Why is that?)
• Max-plus singular values
• The \(k\)-cardinality assignment problem
• Solving the \(k\)-cardinality assignment problem by transformation
• Polynomial convolutions in max-plus algebra

Cited In (4)

• Monge sequences and a simple assignment algorithm
• Completing a (k − 1)-Assignment
• Title not available (Why is that?)
• Algorithms for finding a \(K\)th best valued assignment

This page was built for publication: Computing the sequence of \(k\)-cardinality assignments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2165282)