Algorithms for finding a \(K\)th best valued assignment
type: Item
instance of: scholarly article
title: Algorithms for finding a \(K\)th best valued assignment
zbMATH Open document ID: 0809.90109
DOI: 10.1016/0166-218X(92)00175-L
author: Tomomi Matsui
author: Akihisa Tamura
author: Yoshiko T. Ikebe
published in: Discrete Applied Mathematics
publication date: 1994-07-18T00:00:00Z
review text: In a given bipartite graph with weights \(w(e)\) the problem is considered to find the \(K\)th best valued perfect matchings \(M_ k\). This means that there exist perfect matchings \(M_ 1,\dots, M_{k-1}\) s.t. \(w(M_ 1)<\cdots<w(M_ k)< w(M)\) for all perfect matchings \(M\) with \(w(M)\not\in \{w(M_ 1),\dots, w(M_ k)\}\). The algorithms are based on previous work of Murty (1968) and Chegireddy and Hamacher (1987) which allow equality in the ranking inequalities above. Numerical tests on randomly generated problems show the usefulness of the new approach.
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 590190
zbMATH Keywords: assignment
zbMATH Keywords: bipartite graph
zbMATH Keywords: valued perfect matchings
reviewed by: Horst W. Hamacher
MaRDI profile type: Publication
cites work: Resource constrained assignment problems
cites work: A Lagrangean relaxation method for the constrained assignment problem
cites work: Algorithms for finding k-best perfect matchings
cites work: Programming in networks and graphs. On the combinatorial background and near-equivalence of network flow and matching algorithms
cites work: A Successive Shortest Path Algorithm for The Assignment Problem
cites work: Finding all the perfect matchings in bipartite graphs
cites work: Q5519710
cites work: Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
cites work: Q4040780
description: scientific article; zbMATH DE number 590190