Algorithms for finding a Kth best valued assignment

Tomomi Matsui, Akihisa Tamura, Yoshiko Ikebe

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


We consider a new problem, the Kth best valued assignment problem. Given a bipartite graph G and a cost vector w on its edge set, this is the problem of finding a perfect matching Mk in G such that there exist perfect matchings M1,...,MK-1 satisfying w(M1) < ⋯ < w(MK-1) < w(MK), and w(MK) < w(M) for all perfect matchings M with w(M) ≠ w(M1),...,w(MK). Here w(M) denotes the sum of costs of edges in M. In this paper, we propose two algorithms for solving this problem and verify the efficiency of our algorithms by our preliminary computational experiments.

Original languageEnglish
Pages (from-to)283-296
Number of pages14
JournalDiscrete Applied Mathematics
Issue number3
Publication statusPublished - 1994 May 20
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Algorithms for finding a Kth best valued assignment'. Together they form a unique fingerprint.

Cite this